题目：
Characters in Star Wars each speak a language, but they typically understand a lot more languages that they don’t or can’t speak. For example, Han Solo might speak in Galactic Basic and Chewbacca might respond in Shyriiwook; since they each understand the language spoken by the other, they can communicate just fine like this.

We’ll say two characters can converse if they can exchange messages in both directions. Even if they didn’t understand each other’s languages, two characters can still converse as long as there is a sequence of characters who could translate for them through a sequence of intermediate languages. For example, Jabba the Hutt and R2D2 might be able to converse with some help. Maybe when Jabba spoke in Huttese, Boba Fett could translate to Basic, which R2D2 understands. When R2D2 replies in Binary, maybe Luke could translate to Basic and then Bib Fortuna could translate back to Huttese for Jabba.

In Star Wars Episode IV, there’s a scene with a lot of different characters in a cantina, all speaking different languages. Some pairs of characters may not be able to converse (even if others in the cantina are willing to serve as translators). This can lead to all kinds of problems, fights, questions over who shot first, etc. You’re going to help by asking some of the patrons to leave. The cantina is a business, so you’d like to ask as few as possible to leave. You need to determine the size of the smallest set of characters S such that if all the characters in S leave, all pairs of remaining characters can converse.

For example, in the first sample input below, Chewbacca and Grakchawwaa can converse, but nobody else understands Shyriiwook, so they can’t converse with others in the bar. If they leave, everyone else can converse. In the second sample input, Fran and Ian can converse, as can Polly and Spencer, but no other pairs of characters can converse, so either everyone but Polly and Spencer must leave or everyone but Fran and Ian.

Input
Input starts with a positive integer, 1≤N≤100, the number of characters in the cantina. This is followed by N lines, each line describing a character. Each of these N lines starts with the character’s name (which is distinct), then the language that character speaks, then a list of 0 to 20 additional languages the character understands but doesn’t speak. All characters understand the language they speak. All character and language names are sequences of 1 to 15 letters (a-z and A-Z), numbers, and hyphens. Character names and languages are separated by single spaces.

Output
Print a line of output giving the size of the smallest set of characters S that should be asked to leave so that all remaining pairs of characters can converse.
中文翻译：
在星际交流中，往往由于语言不通所以会导致冲突。每个星球都有自己的语言，比如星球1 能说英语并且能听懂法语（能听懂法语只是能听懂，但不能用法语回答）。星球2能说法语并且能听懂英语，所以他们能交流（星球一说英语后星球二听懂了，用法语回答，星球一也能听懂）。另外一个例子，星球1能说英语并且听的懂法语，但是星球而能说法语但是只能听的懂西班牙语，所以他们不能交流）。题目要求输入N个星球例子，输入星球名字， 能说的语言，能听的懂的语言（能听的懂的语言可以有很多种，但是能说的只能一种）。输入后你的任务是从中挑出最少的不能跟其他交流的星球的个数（意思是踢出这些星球后其他星球都可以交流）。//可以通过第三方交流 星球一说的话如果星球二不懂，但是星球三懂，星球三可以成为中间的翻译。
程序举例：
输入
 6
earth0 French Italian
earth1 English German
earth2 German Italian
earth3 Italian French Spanish
earth4 Spanish Portugese
earth5 Portugese Spanish
输出：
4
//原题链接： https://naq15.

我的想法是根据输入建立有向图，然后找到图中的最大circle，然后用总数减去circle中的元素

你这样不行,如果有两个circle相交,你的结果就是错的

有两个问题，只要和其他所有星球中任意一个不能交流都要踢出吗。如earth0能和earth1交流，但不能和earth2交流，那么earth0和earth2是否都踢出？还是一个星球和其他所有都不能交流才踢出？
再有，确定被踢出的星球允不允许再做翻译？

题目的要求是 最少去掉多少人,才能保证剩下的人交流没有障碍

如果有两个circle相交，如果可以归并则得到较大的。若不能则取最大的circle,则可以保证最多的人数可以交流。其实简化一下思路就是求图中的最强联通部分。

题目已解决，看来基本图论的题大神们不愿意去做，新手们做不出。
基于两次深度优先搜索的c++代码附上，通过ACM系统测验
#include<iostream>
#include<string>
#include<vector>
#include<stack>
#include<cstdio>
#include<algorithm>
#include<sstream>
using namespace std;
//int pop_not(int u,vector<int> vec)
class star_struct
{
public:
  vector<string> lan;
};
class Node
{
  public:
  int node_name;
  int visited;
  Node(int i)
  {
    node_name=i;
    visited=0;
  }
  vector<int> adjnodes;
};
class graph
{
  public:
  int node_num;
  stack<int> st;
  vector<int> temp;
  vector<Node> vertices;
  int can_visit(int u)
  {
    vector<int>::iterator p;
    if(vertices[u].adjnodes.size()==0)
      return 0;
    for(p=vertices[u].adjnodes.begin();p!=vertices[u].adjnodes.end();++p)
      if(vertices[*p].visited==0)
    return 1;
    return 0;
  }
  graph(int num)
  {
    this->node_num=num;
    for(int i=0;i!=num;++i)
      {
    Node node(i);
    vertices.push_back(node);
      }
  }
  void dfs(int u)
  {
    vertices[u].visited=1;
    temp.push_back(u);
    vector<int>::iterator p;
    for(p=vertices[u].adjnodes.begin();p!=vertices[u].adjnodes.end();++p)
      if(!vertices[*p].visited)
         dfs(*p);
    if(!can_visit(u))
      {st.push(u);
    return ;
      }   
  }
  void addedge(int u,int v)
  {
    vertices[u].adjnodes.push_back(v);
  }
  void multidfs(int u)
  {
    dfs(u);
    vector<Node>::iterator p;
    for(p=vertices.begin();p!=vertices.end();++p)
      if(p->visited==0)
    dfs(p->node_name);
  }
};
int comp(string word,vector<string> a)
{
  vector<string>::iterator p;
  p=a.begin()+1;
  for(;p!=a.end();++p)
    {
      if(word==*p)
    return 1;
    }
  return 0;
}
int main(void)
{
  int max;
  string input;
  vector<vector<string> > starwar;
  int n;
  cin>>n;
  int num=n;
  graph g1(n);
  graph g2(n);
  vector<string> temp;
  string word;
  char ch=getchar();
  while(n!=0)
    {
      getline(cin,input);
      istringstream is(input,istringstream::in);
      while(is>>word)
      temp.push_back(word);
      starwar.push_back(temp);
      temp.clear();
      n--;
    }
  for(vector<vector<string> >::iterator q=starwar.begin();q!=starwar.end();++q)
    {
      word=*((*q).begin()+1);
      vector<vector<string> >::iterator p;
      for(p=starwar.begin();p!=starwar.end();++p)
    {
      if(*p==*q)
        continue;
      if(comp(word,*p))
        {g1.addedge(int(q-starwar.begin()),int(p-starwar.begin()));
          // cout<<"g1.addedge "<<int(q-starwar.begin())<<" "<<int(p-starwar.begin())<<endl;
         g2.addedge(int(p-starwar.begin()),int (q-starwar.begin()));
         // cout<<"g2.addedge "<<int(p-starwar.begin())<<" "<<int(q-starwar.begin())<<" "<<endl;
        }
    }
    }
 
g1.multidfs(0);
  while(!g1.st.empty())
    {int u=g1.st.top();
      if(g2.vertices[u].visited==1)
    {g1.st.pop();
      continue;
    }
      g2.dfs(u);
      g1.st.pop();
      /* for(vector<int>::iterator p=g2.temp.begin();p!=g2.temp.end();++p)
    cout<<*p<<" ";
    cout<<endl;*/
      if(g2.temp.size()>max)
    max=g2.temp.size();
      g2.temp.clear();
      
      }
  cout<<num-max<<endl;
  return 0;
}
不懂图论，如何敢说懂算法