# Untitled

a guest
Jul 11th, 2012
99
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. #include <iostream>
2. #include <cstdio>
3. #include <vector>
4. #include <cstring>
5. #include <algorithm>
6. #include <stack>
7. #define MAXN 100005
8. using namespace std;
9.
10. int N,M,R,t1,t2,L,LABEL[MAXN],SIZE[MAXN],S[MAXN],ai,INDEG[MAXN];
11. vector <int> G[MAXN],T[MAXN];
12. vector <pair<int,int> > ans;
13. bool visit[MAXN];
14.
15. void flood(int x){
16.   visit[x] = 1;
17.   for(vector<int>::iterator it=G[x].begin();it!=G[x].end();++it)
18.     if(!visit[*it]) flood(*it);
19.   S[ai++] = x;
20.   G[x].clear();
21. }
22.
23. void kosa(int x){
24.   visit[x] = 1;
25.   LABEL[x] = L;
26.   ++SIZE[L];
27.   for(vector<int>::iterator it=T[x].begin();it!=T[x].end();++it)
28.     if(!visit[*it]) kosa(*it);
29. }
30.
32.   S[ai++] = x;
33.   for(vector<int>::iterator it=G[x].begin();it!=G[x].end();++it)
35.   if(G[x].size() == 0 && S[t1] != x){
36.     ans.push_back(pair<int,int>(x,S[t1]));
37.     t1 = ai-1;
38.   }
39.   --ai;
40.   if(t1 >= ai-1) t1 = ai-1;
41. }
42.
43. void dfs(int x){
44.   for(vector<int>::iterator it=G[x].begin();it!=G[x].end();++it){
45.     dfs(*it);
46.     SIZE[x] += SIZE[*it];
47.   }
48. }
49.
50. int main(){
51.   scanf("%d%d%d",&N,&M,&R);
52.   for(int i=0;i<M;++i){
53.     scanf("%d%d",&t1,&t2);
54.     G[t1].push_back(t2);
55.     T[t2].push_back(t1);
56.   }
57.   flood(R);
58.   memset(visit,0,sizeof(visit));
59.   while(ai){
60.     t1 = S[--ai];
61.     if(!visit[t1]){
62.       ++L;
63.       kosa(t1);
64.     }
65.   }
66.   for(int i=1;i<=N;++i){
67.     for(vector<int>::iterator it=T[i].begin();it!=T[i].end();++it)
68.       if(LABEL[i] != LABEL[*it]){
69.         G[*it].push_back(i);
70.         ++INDEG[i];
71.       }
72.   }
73.   for(int i=1;i<=N;++i) if(INDEG[i] == 0) ai = t1 = 0, link(i);
74.   for(int i=1;i<=N;++i) G[i].clear();
75.   for(int i=1;i<=N;++i){
76.     for(vector<int>::iterator it=T[i].begin();it!=T[i].end();++it)
77.       if(LABEL[i] != LABEL[*it])
78.         G[LABEL[*it]].push_back(LABEL[i]);
79.   }
80.   t1 = 0;
81.   dfs(LABEL[R]);
82.   for(int i=1;i<=N;++i) printf("%d ",SIZE[LABEL[i]]); printf("\n");
83.   printf("%d\n",ans.size());
84.   for(vector<pair<int,int> >::iterator it=ans.begin();it!=ans.end();++it)
85.     printf("%d %d\n",it->first,it->second);
86.   //system("pause");
87. }
RAW Paste Data