Cod sursa(job #2574493)

Utilizator T_george_TGeorge Teodorescu T_george_T Data 5 martie 2020 22:56:20
Problema Componente tare conexe Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.09 kb
#include <bits/stdc++.h>

using namespace std;
ifstream in("ctc.in");
ofstream out("ctc.out");
const int NMAX=100000;
int idx=1,n,m,lowest[NMAX],in_stack[NMAX],val[NMAX];
vector<int>g[NMAX],c;
stack<int>s;
vector<vector<int>>ans;
void tarjan(int node){
    lowest[node]=val[node]=idx++;
    s.push(node);
    in_stack[node]=1;
    for(auto y:g[node])
        if(!val[y])
            tarjan(y),lowest[node]=min(lowest[node],lowest[y]);
        else if(in_stack[y])
            lowest[node]=min(lowest[node],lowest[y]);
    if(lowest[node]==val[node]){
        int n;
        c.clear();
        do{
            c.push_back(n=s.top());
            in_stack[n]=0;
            s.pop();
        }while(n!=node);
        ans.push_back(c);
    }
}
int main()
{
    in>>n>>m;
    for(int i=1,a,b;i<=m;i++){
        in>>a>>b;
        g[a].push_back(b);
    }
    for(int i=1;i<=n;i++)
        if(!val[i])
        tarjan(i);
    out<<ans.size()<<'\n';
    for(int i=0;i<ans.size();i++){
        for(auto y:ans[i])
            out<<y<<" ";
        out<<'\n';
    }
    return 0;
}