Guest User

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.  
  31. void link(int x){
  32.   S[ai++] = x;
  33.   for(vector<int>::iterator it=G[x].begin();it!=G[x].end();++it)
  34.     link(*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