Cod sursa(job #1650827)

Utilizator RobertMMinzat Robert RobertM Data 11 martie 2016 20:43:29
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1 kb
#include <fstream>
#include <vector>
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
int n,m,nr,nrc,aux;
vector<int> x[100001],xt[100001],sol[100001];
bool viz[100001];
int postord[100001];
void dfs(int k){
    viz[k]=1;
    for(int i=0;i<x[k].size();i++)
        if(!viz[x[k][i]])
            dfs(x[k][i]);
    postord[++nr]=k;}
void dfst(int k){
    viz[k]=0;sol[nrc].push_back(k);
    for(int i=0;i<xt[k].size();i++)
        if(viz[xt[k][i]])
            dfst(xt[k][i]);}
void cit(){
    f>>n>>m;
    int i,a,b;
    for(i=1;i<=m;i++){
        f>>a>>b;
        x[a].push_back(b);
        xt[b].push_back(a);}
}
int main()
{
    cit();
    for(int i=1;i<=n;++i)
        if(!viz[i])
            dfs(i);
    for(int i=n;i>0;--i)
        if(viz[postord[i]]){
            ++nrc;
            dfst(postord[i]);}
    g<<nrc<<'\n';
    for(int j=1;j<=nrc;++j){
        for(int i=0;i<sol[j].size();++i)
            g<<sol[j][i]<<" ";
        g<<'\n';}
    return 0;
}