hdu 3639

统计得票最多的人，，投票具有传递性，a->b->c，c就得到两票，刚开始想要是建反图的话直接搜索所有入度为0的点（最大的一定是入度为0的点）答案就出来了，代码敲了一半，才想到一个问题：要是几个人投票形成一个环的话就不好解决了，

如果i个人形成一个环的话，每人都是i-1票，环之间还可以有联系，

明显就是强连通缩点问题，将环缩成点，然后建反图直接搜索，就ok了，

 #include  
#include  
#include  
#define N 5010   
using namespace std; 
int n,m; 
int dfs[N],low[N],belong[N],ins[N],inq[N],num[N],cont[N],vis[N]; 
struct edage 
{ 
    int ed; 
    struct edage *next; 
}*E[N],*e[N]; 
void addedage(int x,int y) 
{ 
    struct edage *p=new edage; 
    p->ed=y; 
    p->next=E[x]; 
    E[x]=p; 
} 
void Addedage(int x,int y) 
{ 
    struct edage *p=new edage; 
    p->ed=y; 
    p->next=e[x]; 
    e[x]=p; 
} 
stackQ; 
int idx,ans; 
void Tarjan(int x) 
{ 
    int v; 
    dfs[x]=low[x]=idx++; 
    Q.push(x); 
    ins[x]=1; 
    for(edage *j=E[x];j;j=j->next) 
    { 
        if(dfs[j->ed]==-1) 
        { 
            Tarjan(j->ed); 
            low[x]=low[x]>low[j->ed] low[j->ed]:low[x]; 
        } 
        else if(ins[j->ed]==1) 
            low[x]=low[x]>dfs[j->ed] dfs[j->ed]:low[x]; 
    } 
    if(low[x]==dfs[x]) 
    { 
        while(1) 
        { 
            v=Q.top(); 
            Q.pop(); 
            ins[v]=0; 
            belong[v]=ans; 
            num[ans]++; 
            if(v==x)break; 
        } 
        ans++; 
    } 
} 
int DFS(int x) 
{ 
    vis[x]=1; 
    int sum=0; 
    for(edage *q=e[x];q;q=q->next) 
        if(vis[q->ed]==0) 
            sum+=(num[q->ed]+DFS(q->ed)); 
        return sum; 
} 
int main() 
{ 
    int i,j,x,op=1,t,y; 
    scanf("%d",&t); 
    while(t--) 
    { 
        memset(E,NULL,sizeof(E)); 
        memset(e,NULL,sizeof(e)); 
        memset(dfs,-1,sizeof(dfs)); 
        memset(ins,0,sizeof(ins)); 
        memset(inq,0,sizeof(inq)); 
        memset(num,0,sizeof(num)); 
        memset(cont,0,sizeof(cont)); 
        scanf("%d%d",&n,&m); 
        for(i=0;inext) 
            { 
                if(belong[i]!=belong[q->ed]) 
                { 
                    inq[belong[i]]++; 
                    Addedage(belong[q->ed],belong[i]);//建反图  
                } 
            } 
        } 
        int max=-1; 
        for(i=0;i
#include
#include
#define N 5010
using namespace std;
int n,m;
int dfs[N],low[N],belong[N],ins[N],inq[N],num[N],cont[N],vis[N];
struct edage
{
 int ed;
 struct edage *next;
}*E[N],*e[N];
void addedage(int x,int y)
{
 struct edage *p=new edage;
 p->ed=y;
 p->next=E[x];
 E[x]=p;
}
void Addedage(int x,int y)
{
 struct edage *p=new edage;
 p->ed=y;
 p->next=e[x];
 e[x]=p;
}
stackQ;
int idx,ans;
void Tarjan(int x)
{
 int v;
 dfs[x]=low[x]=idx++;
 Q.push(x);
 ins[x]=1;
 for(edage *j=E[x];j;j=j->next)
 {
  if(dfs[j->ed]==-1)
  {
   Tarjan(j->ed);
   low[x]=low[x]>low[j->ed] low[j->ed]:low[x];
  }
  else if(ins[j->ed]==1)
   low[x]=low[x]>dfs[j->ed] dfs[j->ed]:low[x];
 }
 if(low[x]==dfs[x])
 {
  while(1)
  {
   v=Q.top();
   Q.pop();
   ins[v]=0;
   belong[v]=ans;
   num[ans]++;
   if(v==x)break;
  }
  ans++;
 }
}
int DFS(int x)
{
 vis[x]=1;
 int sum=0;
 for(edage *q=e[x];q;q=q->next)
  if(vis[q->ed]==0)
   sum+=(num[q->ed]+DFS(q->ed));
  return sum;
}
int main()
{
 int i,j,x,op=1,t,y;
 scanf("%d",&t);
 while(t--)
 {
  memset(E,NULL,sizeof(E));
  memset(e,NULL,sizeof(e));
  memset(dfs,-1,sizeof(dfs));
  memset(ins,0,sizeof(ins));
  memset(inq,0,sizeof(inq));
  memset(num,0,sizeof(num));
  memset(cont,0,sizeof(cont));
  scanf("%d%d",&n,&m);
  for(i=0;inext)
   {
    if(belong[i]!=belong[q->ed])
    {
     inq[belong[i]]++;
     Addedage(belong[q->ed],belong[i]);//建反图
    }
   }
  }
  int max=-1;
  for(i=0;i