Cod sursa(job #2760881)

Utilizator RobertAcAcatrinei Robert-Marian RobertAc Data 29 iunie 2021 13:51:44
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.32 kb
#include <bits/stdc++.h>
#define nmax 100001
using namespace std;
ifstream in("ctc.in");
ofstream out("ctc.out");
struct node{
    int index,lowlink;
    node(){
        index=lowlink=0;
    }
};
int ind=0;
vector<node> noduri(nmax);
vector<int> graf[nmax];
vector<bool> viz(nmax,0);
stack<int> s;
vector<vector<int>> ans;
vector<bool> onStack(nmax,0);
void dfs(int nod){
    noduri[nod].index=noduri[nod].lowlink=ind++;
    s.push(nod);
    onStack[nod]=1;
    viz[nod]=1;
    for(auto i:graf[nod]){
        if(!viz[i]){
            dfs(i);
            noduri[nod].lowlink=min(noduri[i].lowlink,noduri[nod].lowlink);
        }else if(onStack[i])noduri[nod].lowlink=min(noduri[i].index,noduri[nod].lowlink);
    }
    if(noduri[nod].index==noduri[nod].lowlink){
        vector<int> tmp;
        int i;
        do{
            i=s.top();
            s.pop();
            onStack[i]=0;
            tmp.push_back(i);
        }while(i!=nod);
        ans.push_back(tmp);
    }
}
int main(){
    int n,m;
    in>>n>>m;
    for(;m;m--){
        int x,y;
        in>>x>>y;
        graf[x].push_back(y);
    }
    for(int i=1;i<=n;i++){
        if(!viz[i])dfs(i);
    }
    out<<ans.size()<<'\n';
    for(auto i:ans){
        for(auto j:i){
            out<<j<<' ';
        }
        out<<'\n';
    }

}