Cod sursa(job #2129362)

Utilizator Andrei2000Andrei Mihailescu Andrei2000 Data 12 februarie 2018 19:23:05
Problema Componente tare conexe Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 0.98 kb
#include <bits/stdc++.h>

using namespace std;

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

const int nmax=100002;

vector< vector<int> > Q;
vector <int> G[nmax];
stack <int> stk;

int n,m,v[nmax],l[nmax],k=1,a;

void str(int no){
    v[no]=l[no]=k++;
    stk.push(no);
    for(auto q: G[no])
        if(!v[q]){
            str(q);
            l[no]=min(l[no],l[q]);
        }
        else
            l[no]=min(l[no],v[q]);
    if(l[no]>=v[no]){
        vector <int> x;
        do{
            x.push_back(a=stk.top());
            stk.pop();
        }
        while(a!=no);
        Q.push_back(x);
    }
}

int main()
{
    int aa,b;
    fin>>n>>m;
    for(int i=1;i<=m;++i){
        fin>>aa>>b;
        G[aa].push_back(b);
    }
    for(int i=1;i<=n;++i)if(!v[i])str(i);
    fout<<Q.size()<<'\n';
    for(int i=0;i<Q.size();++i){
        for(int j=0;j<Q[i].size();++j)
            fout<<Q[i][j]<<' ';
        fout<<'\n';
    }
    return 0;
}