Cod sursa(job #1850382)

Utilizator NineshadowCarapcea Antonio Nineshadow Data 18 ianuarie 2017 17:04:36
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.24 kb
#include <bits/stdc++.h>
#define MAXN 400005
using namespace std;
ifstream in("ctc.in");
ofstream out("ctc.out");
int n,m,k;
vector<int> v[MAXN],r;
vector< vector<int> > CTC;
stack<int> s;
int id[MAXN],lowlink[MAXN];
bool in_stack[MAXN];

void tarjan(int nod)
{
    id[nod]=lowlink[nod]=k;
    k++;
    s.push(nod);
    in_stack[nod]=1;
    for(int i : v[nod])
    {
        if(id[i]==-1)
        {
            tarjan(i);
            lowlink[nod]=min(lowlink[nod],lowlink[i]);
        }
        else if(in_stack[i])
            lowlink[nod]=min(lowlink[nod],lowlink[i]);
    }
    if(id[nod]==lowlink[nod])
    {
        r.clear();
        int t;
        do{
            r.push_back(t=s.top());
            s.pop();
            in_stack[t]=0;
        }while(t!=nod);
        CTC.push_back(r);
    }

}
int main()
{
    in>>n>>m;
    for(int i=0;i<m;++i)
    {
        int x,y;
        in>>x>>y;
        v[x-1].push_back(y-1);
    }
    memset(id,-1,MAXN);
    for(int i=0;i<n;++i)
        if(id[i]==-1)
            tarjan(i);
    out<<CTC.size()<<'\n';
    for(int i=0;i<CTC.size();++i)
    {
        for(int j=0;j<CTC[i].size();++j)
            out<<CTC[i][j]+1<<' ';
        out<<'\n';
    }
    return 0;
}