Cod sursa(job #2252865)

Utilizator IsacLucianIsac Lucian IsacLucian Data 3 octombrie 2018 10:46:35
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.02 kb
#include <bits/stdc++.h>

using namespace std;

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

const int Nmax=1e5+2;

int n,m,k,nrc;
int st[Nmax];
bitset<Nmax>viz;
vector<int>L[Nmax],G[Nmax],ans[Nmax];


void Sortare_T(int nod)
{
    viz[nod]=1;
    for(auto i:L[nod])
        if(!viz[i])
            Sortare_T(i);

    st[++k]=nod;
}

void Dfs(int nod)
{
    viz[nod]=1;
    for(auto i:G[nod])
        if(!viz[i])Dfs(i);

    ans[nrc].push_back(nod);
}

int main()
{
    fin>>n>>m;

    int x,y;
    for(int i=1;i<=m;i++)
    {
        fin>>x>>y;
        L[x].push_back(y);
        G[y].push_back(x);
    }

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


    viz.reset();

    for(int i=n;i>=1;i--)
        if(!viz[st[i]])
        {
            nrc++;
            Dfs(st[i]);
        }

    fout<<nrc<<"\n";

    for(int i=1;i<=nrc;i++,fout<<"\n")
        for(auto j:ans[i])
            fout<<j<<" ";

    fin.close();
    fout.close();
    return 0;
}