Cod sursa(job #2419178)

Utilizator capmareAlexCapmare Alex capmareAlex Data 7 mai 2019 19:06:53
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.02 kb
#include <bits/stdc++.h>
#define NMAX 100001
#define pb push_back
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int n, m;
vector < int > v[NMAX], g[NMAX],sol[NMAX];
int used[ NMAX],comp;
deque < int > q;
void dfs( int k)
{
    used[k] = true;
    for(auto x : v[k])
        if(!used[x]) dfs(x);
    q.pb(k);
}
void dfsT(int k)
{
    sol[comp].push_back(k);
    used[k] = true;
    for( auto x : g[k])
        if(!used[x])dfsT(x);
}
int main()
{
    fin >> n >> m;
    while ( m )
    {
        int x, y;
        fin >>x >>y;
        v[x].pb(y);
        g[y].pb(x);
        --m;
    }
    for( int i = 1; i <= n; ++i)
        if(!used[i])dfs(i);

    memset(used, false, sizeof(used) );
    int t;
    while ( q.size())
    {
        t=q.back();
        q.pop_back();
        if(!used[t])
        {
            ++comp;
            dfsT(t);
        }
    }
    fout<<comp<<"\n";
    for(int i=1;i<=comp;++i,fout<<"\n")
        for(auto x : sol[i])fout<<x<<" ";

}