题目大意：比较搞笑，就是一头牛仰慕另一头牛，也可能会仰慕别的一堆牛。问你是不是会有那么几个牛，是除了他之外别的牛都仰慕的。求出这样的牛的个数。
构图，发现按问题性质，如果有一堆牛互相仰慕的，别且这堆牛被这一堆之外的牛都仰慕，很明显这堆牛就是解的一部分，抽象出来就是原图的极大连通子图可以收缩为一个点处理，最后在有向无环图上求出是否有某个点的可达性为n-1，那么这个点映射到原图上的点集的点个数即为所求。
注意如果新图是由一个以上不相交子图的并构成，那么解必为0。（其实大家都注意了就我没注意。。。）
解法： 构图，标记强分量，枚举边构造缩点新图，新图中枚举深搜起点，判断可达性。
关于性能，点多边少，可以选择邻接表存放，使用STL的set结构可以将判重边的时间降到logn。
1
#include<stdio.h>
2#include<stdlib.h>
3#include<string.h>
4
5#define MAXV 100000
6 int postR[MAXV],post[MAXV];
7 int cnt0,cnt1;
8
9typedef struct LinkNod *Link;
10
struct LinkNod
{
11
int dest;
12 Link next;
13
};
14
15typedef struct GraphNod *Graph;
16struct GraphNod{
17 Link v[MAXV];
18 int vnum;
19 int id[MAXV]; // 分量标号
20 int hash[MAXV]; // 保存缩点数
21};
22Graph G,GR,Gch;
23
24int visit[MAXV];
25bool have,star;
26int chNum,visiNum;
27int degree[MAXV];
28
29void DFS_1(Graph g,int w);
30void DFS_bui(Graph g,Graph ch);
31void DFS_ans(Graph g,int w);
32
33int main(){
34 int i,j,k;
35 int a,b;
36 int n,m;
37 int id;
38 Link pos,tmpPos;
39
40 G = (Graph)malloc(sizeof(struct GraphNod));
41 GR = (Graph)malloc(sizeof(struct GraphNod));
42 Gch = (Graph)malloc(sizeof(struct GraphNod));
43
while(scanf("%d%d",&n,&m)!=EOF){
44 G->vnum = GR->vnum = Gch->vnum = n;
45 memset(G,0,sizeof(int)*(n+1));
46 memset(GR,0,sizeof(int)*(n+1));
47 memset(Gch,0,sizeof(int)*(n+1));
48 for(i=0;i<m;i++){
49 scanf("%d%d",&a,&b); a--; b--;
50 // 原图
51 pos=G->v[b];
52 pos = (Link)malloc(sizeof(struct LinkNod));
53 pos->dest =a; pos->next=G->v[b];
54 G->v[b]=pos;
55 // 逆图
56 pos=GR->v[a];
57 pos = (Link)malloc(sizeof(struct LinkNod));
58 pos->dest =b; pos->next=GR->v[a];
59 GR->v[a]=pos;
60
}
61 memset(G->id,-1,sizeof(int)*(G->vnum+1));
62 memset(GR->id,-1,sizeof(int)*(GR->vnum+1));
63 memset(Gch->id,-1,sizeof(int)*(Gch->vnum+1));
64 memset(G->hash,0,sizeof(int)*(G->vnum+1));
65 memset(GR->hash,0,sizeof(int)*(GR->vnum+1));
66 memset(Gch->hash,0,sizeof(int)*(Gch->vnum+1));
67 cnt1=cnt0=0;
68
69 for(i=0;i<GR->vnum;i++)
70 if( GR->id[i]==-1 ) DFS_1(GR,i);
71
72
73 for(i=0;i<cnt0;i++) { postR[i] = post[i];}
74
75 for(cnt1=0,i=cnt0-1;i>-1;i--)
76 if(G->id[postR[i]]==-1){ DFS_1(G,postR[i]); cnt1++; }
77
78 Gch->vnum=cnt1;
79 memset(degree,0,sizeof(int)*(Gch->vnum));
80 DFS_bui(G,Gch);
81
82 star=false;
83 for(i=Gch->vnum-1;i>-1;i--) if(degree[i]==0){
84 visiNum=0; memset(visit,0,sizeof(int)*(Gch->vnum));
85 DFS_ans(Gch,i);
86 if( visiNum == Gch->vnum ){ printf("%d\n",G->hash[i]); star=true; break; }
87 }
88 if( star == false ) printf("0\n");
89
90 }
91 return 0;
92}
93
94void DFS_1(Graph g,int w){
95 g->id[w] = cnt1; g->hash[cnt1]++; //printf("%d点染色为 %d\n",w+1,cnt1);
96 for( Link pos = g->v[w]; pos!=NULL; pos=pos->next ) if( g->id[ pos->dest ] == -1 ) DFS_1(g,pos->dest);
97 post[cnt0++] = w; // 后序编码
98}
99
100void DFS_ans(Graph g,int w){
101 visiNum++; visit[w]=1;
102 for( Link pos = g->v[w]; pos!=NULL; pos=pos->next ) if( !visit[pos->dest] ) { DFS_ans(g,pos->dest); }
103 return ;
104}
105
106void DFS_bui(Graph g,Graph ch){
107 Link pos,pos2,tmp;
108 int i;
109 for(i=0;i<g->vnum;i++)
110 for(pos=g->v[i];pos;pos=pos->next){
111 if( g->id[i] != g->id[pos->dest] ){
112 pos2=ch->v[ g->id[i] ]; have=0;
113 while(pos2){
114 if( pos2->dest == g->id[ pos->dest ] ){ have=1; break; }
115 pos2=pos2->next;
116 }
117 if( have ==0 ){
118 tmp = (Link)malloc(sizeof(struct LinkNod));
119 tmp->dest = g->id[ pos->dest ]; tmp->next = ch->v[ g->id[i] ];
120 ch->v[ g->id[i] ] = tmp;
121 degree[ g->id[ pos->dest ]]++;
122 }
123 }
124 }
125 return ;
126}