Cod sursa(job #1795412)

Utilizator cameleonGeorgescu Dan cameleon Data 2 noiembrie 2016 13:22:43
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.29 kb
//complxitate O(n+m)
#include <fstream>
#include<vector>
#include<stack>
#include<algorithm>
#define Nmax 100005
using namespace std;

ifstream fin("ctc.in");
ofstream fout("ctc.out");

int n;
bool vg[Nmax],vgt[Nmax];
vector <int> g[Nmax],gt[Nmax],c[Nmax];
stack  <int> s;

void citeste(){
    int m,x,y;
    fin>>n>>m;
    for(int i=1;i<=m;i++){
        fin>>x>>y;
        g[x].push_back(y);
        gt[y].push_back(x);
    }
}
void dfs1(int x){
    vg[x]=1;
    for(unsigned int i=0;i<g[x].size();i++)
        if(vg[g[x][i]]==0){
            dfs1(g[x][i]);
    }
    s.push(x);
}

void dfs2(int x,int nr){
    vgt[x]=1;
    c[nr].push_back(x);

    for(unsigned int i=0;i<gt[x].size();i++)
        if(vgt[gt[x][i]]==0){
            dfs2(gt[x][i],nr);
    }

}
int main()
{
    int i,nr=0;
    citeste();
    for(i=1;i<=n;i++)
        if(vg[i]==0){
            dfs1(i);

            }

    while(!s.empty()){
          i=s.top();
          s.pop();
          if(vgt[i]==0){
              dfs2(i,nr);
               nr++;
          }
    }
    fout<<nr<<"\n";
    for(i=0;i<nr;i++){
        sort(c[i].begin(),c[i].end());
        for(unsigned int j=0;j<c[i].size();j++)
            fout<<c[i][j]<<" ";
        fout<<"\n";
    }

   return 0;
}