Cod sursa(job #3260391)

Utilizator Dragos__1_1Dragos Antohi Dragos__1_1 Data 2 decembrie 2024 10:48:04
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.99 kb
#include <bits/stdc++.h>
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
int n,i,j,m,viz[100005],st[100005],len,comp,a,b;
vector<int>C[100005],L[100005],T[100005];
void dfs(int node){
    viz[node]=1;
    for (auto it:L[node]){
        if (!viz[it]){
            dfs(it);
        }
    }
    st[++len]=node;
}
void DFS(int node){
    viz[node]=0;
    C[comp].push_back(node);
    for (auto it:T[node]){
        if (viz[it]){
            DFS(it);
        }
    }
}
int main()
{   f>>n>>m;
    for (i=1;i<=m;i++){
        f>>a>>b;
        L[a].push_back(b);
        T[b].push_back(a);
    }
    for (i=1;i<=n;i++){
        if (!viz[i]){
            dfs(i);
        }
    }
    for (i=1;i<=n;i++){
        int k=st[n-i+1];
        if (viz[k]){
            comp++;
            DFS(k);
        }
    }
    g<<comp<<'\n';
    for (i=1;i<=comp;i++){
        for (auto it:C[i]){
            g<<it<<' ';
        }
        g<<'\n';
    }
    return 0;
}