Cod sursa(job #2206878)

Utilizator andreiudilaUdila Andrei andreiudila Data 24 mai 2018 09:00:15
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.18 kb
#include <fstream>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
ifstream cin("ctc.in");
ofstream cout("ctc.out");

vector <int> g[100010],gt[100010];
vector <int> sol[100010];
int nodes[100010],f[100010];
bool viz[100010];
int nrs,i,j,n,m,x,y,timp,nrn;

bool cmp(int a, int b)
{
    return f[a]<f[b];
}
void dfs(int nod)
{
    viz[nod]=1;
    f[nod]=timp;

    for(auto node : g[nod])
        if(!viz[node])
        {
            dfs(node);
        }

    nodes[++nrn] = nod;
}

void dfs2(int nod)
{
    viz[nod]=1;
    sol[nrs].push_back(nod);

    for(auto node : gt[nod])
        if(!viz[node])
        {
            dfs2(node);
        }
}


int main()
{
    cin>>n>>m;
    for(i=1; i<=m; ++i)
    {
        cin>>x>>y;
        g[x].push_back(y);
        gt[y].push_back(x);
    }

    for(i=1; i<=n; ++i)
        if(!viz[i])
            dfs(i);

    memset(viz,0,sizeof(viz));
    for(i=n;i>=1;--i)
        if(!viz[nodes[i]])
    {
        ++nrs;
        dfs2(nodes[i]);
    }

    cout<<nrs<<"\n";
    for(i=1;i<=nrs;++i,cout<<"\n")
        for(auto x : sol[i]) cout<<x<<" ";


    return 0;
}