Cod sursa(job #2666601)

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

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

typedef vector<int> vi;
typedef vector<bool> vb;

const int oo=INT_MAX/2;

int n,m,k;
vector<vector<int>> g;
// vector<vector<int>> gr; // graph


vector<vector<int>> con;
vector<int> rd;
vector<bool> onStk;
deque<int> stk;

int tarjan(int cr, int dep=1){
    rd[cr]=dep;
    onStk[cr]=1;
    stk.push_back(cr);
    cout<<"mih\n";
    for(int nx:g[cr]){
        if(rd[nx]==oo)
            rd[cr]=min(rd[cr],tarjan(nx,dep+1));
        else if(onStk[nx])
            rd[cr]=min(rd[cr],rd[nx]);
    }
    if(dep==rd[cr]){
        con.push_back(vector<int>());
        do {
            cout<<stk.back()<<"\n";
            con[con.size()-1].push_back(stk.back());
            onStk[stk.back()]=0;
            stk.pop_back();
        }
        while(stk.back()!=cr);
    }
    return rd[cr];
}

int main(){
    fin>>n>>m;
    g.resize(n+1), rd.resize(n+1,oo), onStk.resize(n+1,0);
    for(int i=m;i--;){
        int x,y;
        fin>>x>>y;
        g[x].push_back(y);
    }
    tarjan(1);
    fout<<con.size()<<"\n";
    for(int i=0;i<con.size();++i){
        for(int j=0; j<con[i].size();++j)
            fout<<con[i][j]<<" ";
        fout<<"\n";
    }

}