Cod sursa(job #2666776)

Utilizator mihhTURCU MIHNEA ALEXANDRU mihh Data 2 noiembrie 2020 14:59:15
Problema Componente tare conexe Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.23 kb
#include<bits/stdc++.h>
using namespace std;

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

const int oo=INT_MAX/2;

typedef vector<int> vi;

int n,m,k;
vector<vi> g;

vi lowlink, idx, inStk;
vi stk;

vector<vi> ctcs;

void tarjan(int nd, int id=1){
    lowlink[nd]=idx[nd]=id;
    inStk[nd]=1;
    stk.push_back(nd);

    for(auto vc:g[nd]){
        if(idx[vc]==0){
            tarjan(vc,id+1);
            lowlink[nd]=min(lowlink[nd],lowlink[vc]);
        }
        else if(inStk[vc]){
            lowlink[nd]=min(lowlink[nd],lowlink[vc]);
        }
    }
    if(lowlink[nd]==idx[nd]){
        cout<<nd<<"\n\n";
        ctcs.push_back(vi());
        int aux;
        do {
            ctcs.back().push_back(aux=stk.back());
            inStk[stk.back()]=0;
            stk.pop_back();
        }
        while(aux!=nd);
    }
}

int main(){
    fin>>n>>m;
    g.resize(n+1), lowlink.resize(n+1), idx.resize(n+1,0), inStk.resize(n+1,0);
    for(int i=m;i--;){
        int x,y; fin>>x>>y;
        g[x].push_back(y);
    }
    for(int i=1;i<=n;++i)
        if(idx[i]==0) tarjan(i);
    fout<<ctcs.size()<<"\n";
    for(int i=0;i<ctcs.size();++i){
        for(int j=0; j<ctcs[i].size(); ++j)
            fout<<ctcs[i][j]<<" ";
        fout<<"\n";
    }

}