Cod sursa(job #3226901)

Utilizator Simon2712Simon Slanina Simon2712 Data 23 aprilie 2024 11:37:04
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.04 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
const int N=1e5+1;
vector<int> a[N],b[N];
int v[N],vc[N];
int ind=0;
void dfs(int nod)
{
    vc[nod]=1;
    for(auto nod2:a[nod])
    {
        if(!vc[nod2])
            dfs(nod2);
    }
    ind++;
    v[ind]=nod;
}
int k=0;
vector<int> ctc[N];
void dfstranspus(int nod)
{
    vc[nod]=1;
    ctc[k].push_back(nod);
    for(auto nod2:b[nod])
        if(!vc[nod2])
            dfstranspus(nod2);
}
int main()
{
    int n,m,i,x,y;
    fin>>n>>m;
    for(i=0;i<m;i++)
    {
        fin>>x>>y;
        a[x].push_back(y);
        b[y].push_back(x);
    }
    for(i=1;i<=n;i++)
        if(!vc[i])
            dfs(i);
    for(i=1;i<=n;i++)
        vc[i]=0;
    for(i=n;i>0;i--)
    {
        if(!vc[v[i]]){
            k++;
            dfstranspus(v[i]);
        }
    }
    fout<<k<<'\n';
    for(i=1;i<=k;i++)
    {
        for(auto nod:ctc[i])
            fout<<nod<<" ";
        fout<<'\n';
    }
    return 0;
}