Cod sursa(job #3232274)

Utilizator diana_dd03Dorneanu Diana diana_dd03 Data 29 mai 2024 17:42:09
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.29 kb
#include <bits/stdc++.h>
using namespace std;

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

int n, m, t, cc;
vector<int>ad[100005];
vector<int>ctc[100005];
vector<int>disc;
vector<int>pr;
vector<int>vis;
vector<int>acc;
vector<int>c;
stack<int>s;

void dfs(int nod){
    vis[nod]=1;
    pr[nod]=1;
    s.push(nod);
    disc[nod]=acc[nod]=++t;
    for(auto i : ad[nod]){
        if(!vis[i]){
            dfs(i);
            acc[nod]=min(acc[nod], acc[i]);
        }
        else
            if(pr[i])
                acc[nod]=min(acc[nod], acc[i]);
    }
    if(acc[nod]==disc[nod]){
        cc++;
        while(s.top()!=nod){
            pr[s.top()]=0;
            ctc[cc].push_back(s.top());
            s.pop();
        }
        pr[s.top()]=0;
        ctc[cc].push_back(s.top());
        s.pop();
    }

}

int main(){
    fin>>n>>m;
    for(int i=1;i<=m;i++){
        int x, y;
        fin>>x>>y;
        ad[x].push_back(y);
    }
    vis.assign(n+1, 0);
    pr.assign(n+1, 0);
    acc.assign(n+1, 0);
    disc.assign(n+1, 0);
    for(int i=1;i<=n;i++)
        if(!vis[i])
            dfs(i);

    fout<<cc<<"\n";
    for(int i=1;i<=cc;i++){
        for(auto e : ctc[i])
            fout<<e<<" ";
        fout<<'\n';
    }
    return 0;
}