Cod sursa(job #2888842)

Utilizator iuliavIulia Vincze iuliav Data 11 aprilie 2022 21:34:13
Problema Componente tare conexe Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.05 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

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

int n,m,c=0;
vector<int> o,v[100005],adj[100005],rev_adj[100005];
vector<bool> viz;

void dfs1(int nod)
{
    viz[nod]=1;
    for(int x:adj[nod])
        if(!viz[x]) dfs1(x);
    o.push_back(nod);
}

void dfs2(int nod)
{
    viz[nod]=1;
    v[c].push_back(nod);
    for(int x:rev_adj[nod])
        if(!viz[x]) dfs2(x);
}

int main()
{
    fin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int a, b;
        fin>>a>>b;
        adj[a].push_back(b);
        rev_adj[b].push_back(a);
    }

    viz.assign(n+5, 0);
    for(int i=1;i<=n;i++)
    {
        if(!viz[i]) dfs1(i);
    }
    reverse(o.begin(),o.end());
    viz.assign(n+5, 0);
    for(int x:o)
    {
        if(!viz[x]){c++;dfs2(x);}
    }
    fout<<c<<endl;
    for(int i=1;i<=c;i++)
    {
        for(int x:v[i])
        {
            fout<<x<<' ';
        }
        fout<<endl;
    }
    return 0;
}