Cod sursa(job #1725379)

Utilizator AcuasPopescu Nicolae-Aurelian Acuas Data 5 iulie 2016 16:07:47
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.3 kb
#include <fstream>
#include <stack>
#include <algorithm>
#include <vector>
#define NMAX 100005
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
vector<int> G[NMAX],GT[NMAX],ras[NMAX];
int viz[NMAX];
stack<int> s;
int n,m;
void citire(){
    f>>n>>m;
    int i,x,y;
    for(i=1;i<=m;i++){
        f>>x>>y;
        G[x].push_back(y);
        GT[y].push_back(x);
    }
}
void DFS(int x){
    viz[x]=1;
    for(vector<int>::iterator it=G[x].begin();it!=G[x].end();it++)
        if(viz[*it]==0)
            DFS(*it);
    s.push(x);
}
void tranDFS(int x,int nr){
    viz[x]=1;
    ras[nr].push_back(x);
    for(vector<int>::iterator it=GT[x].begin();it!=GT[x].end();it++)
        if(viz[*it]==0)
            tranDFS(*it,nr);
}
int main(){
    citire();
    int i;
    for(i=1;i<=n;i++){
        if(viz[i]==0)
            DFS(i);
    }
    fill(viz+1,viz+1+n,NULL);
    int contor=0;
    while(!s.empty()){
        if(viz[s.top()]==0){
            ++contor;
            tranDFS(s.top(),contor);
        }
        s.pop();
    }
    g<<contor<<'\n';
    for(i=1;i<=contor;i++){
        sort(ras[i].begin(),ras[i].end());
        for(vector<int>::iterator it=ras[i].begin();it!=ras[i].end();it++)
            g<<*it<<' ';
        g<<'\n';
    }
    return 0;
}