Cod sursa(job #1193429)

Utilizator buzu.tudor67Tudor Buzu buzu.tudor67 Data 31 mai 2014 18:52:32
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.56 kb
#include<fstream>
#include<vector>
#include<stack>
using namespace std;
ifstream fi("ctc.in");
ofstream fo("ctc.out");

const int maxn = 100005;

vector<int> a[maxn];//graful initial
vector<int> b[maxn];//graful transpus
vector<int> ctc[maxn];
stack<int> st;

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

void dfs_graf_initial(int nod){
     int i;
     
     viz[nod]=1;
     for(i=0;i<(int)a[nod].size();i++)
       if(!viz[a[nod][i]]) dfs_graf_initial(a[nod][i]);
       
     st.push(nod);
}

void dfs_graf_transpus(int nod){
     int i;
     
     viz[nod]=1;
     ctc[nr].push_back(nod);
     
     for(i=0;i<(int)b[nod].size();i++)
       if(!viz[b[nod][i]]) dfs_graf_transpus(b[nod][i]);
}

int main(){
    fi>>n>>m;
    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++) viz[i]=0;
    for(i=1;i<=n;i++)
      if(!viz[i]) dfs_graf_initial(i);
    
    for(i=1;i<=n;i++) viz[i]=0;
    while(st.size()){ 
                     x=st.top(); 
                     
                     if(!viz[x]){
                                 nr++;
                                 dfs_graf_transpus(x);
                                }
                     
                     st.pop(); 
                    }
    
    fo<<nr<<"\n";
    for(i=1;i<=nr;i++)
       {
        for(j=0;j<(int)ctc[i].size();j++) fo<<ctc[i][j]<<" ";
        fo<<"\n";
       }
      
    fi.close();
    fo.close();
    return 0;
}