Cod sursa(job #2734286)

Utilizator Ioana_GaborGabor Ioana Ioana_Gabor Data 31 martie 2021 17:37:54
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.29 kb

#include <bits/stdc++.h>
#define NMAX 100000

using namespace std;

ifstream fi("ctc.in");
ofstream fo("ctc.out");

int n,m,x,y;
vector<int> G[NMAX+5],aux;
vector<vector<int>> comp;
int low[NMAX+5],ind[NMAX+5];
int st[NMAX+5],top;
int inst[NMAX+5];
int idx;

void tarjan(int nod){
    low[nod]=ind[nod]=++idx;
    st[++top]=nod;
    inst[nod]=1;
    for(auto y:G[nod]){
        if(ind[y]==0){
            tarjan(y);
            low[nod]=min(low[nod],low[y]);
        }else if(inst[y]){
            low[nod]=min(low[nod],low[y]);
        }
    }
    if(low[nod]==ind[nod]){
        aux.clear();
        while(top&&st[top]!=nod){
            aux.push_back(st[top]);
            inst[st[top]]=0;            
            top--;
        }
        aux.push_back(st[top]);
        inst[st[top]]=0;
        top--;
        sort(aux.begin(),aux.end());
        comp.push_back(aux);
    }
}

int main(){
    fi>>n>>m;
    for(int i=1;i<=m;i++){
        fi>>x>>y;
        G[x].push_back(y);
    }
    for(int i=1;i<=n;i++){
        ind[i]=0;
    }
    for(int i=1;i<=n;i++){
        if(!ind[i]){
            tarjan(i);
        }
    }
    sort(comp.begin(),comp.end());
    fo<<comp.size()<<'\n';
    for(auto c:comp){
        for(auto v:c){
            fo<<v<<' ';
        }
        fo<<'\n';
    }
    fi.close();
    fo.close();
}