Cod sursa(job #1076219)

Utilizator buzu.tudor67Tudor Buzu buzu.tudor67 Data 9 ianuarie 2014 23:05:23
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.66 kb
#include<fstream>
#include<vector>
#include<stack>
#define maxn 100005
using namespace std;
ifstream fi("ctc.in");
ofstream fo("ctc.out");

vector <int> a[maxn],b[maxn],c[maxn];
stack <int> st;

int i,n,m,x,y,nr=0;
bool viz[maxn];

void dfs1(int k){
     viz[k]=1;
     
     while(a[k].size())
       {
        if(viz[a[k].back()]==0) dfs1(a[k].back());
        a[k].pop_back();
       }
       
     st.push(k);
}

//dfs2 - pentru graful transpus
void dfs2(int k){
     viz[k]=1;
     
     while(b[k].size())
       {
        if(viz[b[k].back()]==0){
                                c[nr].push_back(b[k].back());
                                dfs2(b[k].back());
                               }
        b[k].pop_back();
       }
}

int main(){
    fi>>n>>m;
    
    for(i=1;i<=n;i++) viz[i]=0;
    
    for(i=1;i<=m;i++)
      {
       fi>>x>>y;
       a[x].push_back(y);
       b[y].push_back(x);
      }
    
    for(i=1;i<=n;i++)
      if(viz[i]==0) dfs1(i);
    
    for(i=1;i<=n;i++) viz[i]=0;
    
    while(st.size())
      {
       if(viz[st.top()]==0){
                            nr++;
                            c[nr].push_back(st.top());
                            dfs2(st.top());
                           }
       st.pop();
      }
    
    fo<<nr<<"\n";
    for(i=1;i<=nr;i++){
                       while(c[i].size()){
                                          fo<<c[i].back()<<" ";
                                          c[i].pop_back();
                                         }
                       fo<<"\n";
                      }
    
    fi.close();
    fo.close();
    return 0;
}