Cod sursa(job #1832181)

Utilizator MithrilBratu Andrei Mithril Data 19 decembrie 2016 16:08:49
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.2 kb
#include <bits/stdc++.h>
using namespace std;

ifstream fin("ctc.in");
ofstream fout("ctc.out");
vector<bool> onStack;
vector<int> dis,low;
vector<int> G[100001],comp[100001];
int n,m,x,y,ind=1,cnt,topStack;
stack<int> S;
void strongConnect(int);

int main()
{
    fin>>n>>m;
    onStack.resize(n+1,false);
    dis.resize(n+1,-1);
    low.resize(n+1,-1);

    for(int i=1;i<=m;i+=1)
    {
        fin>>x>>y;
        G[x].push_back(y);
    }

    for(int i=1;i<=n;i+=1)if(dis[i]==-1)
        strongConnect(i);
    fout<<cnt<<'\n';
    for(int i=1;i<=cnt;i+=1)
    {
        for(auto j:comp[i])fout<<j<<' ';
        fout<<'\n';
    }
    return 0;
}

void strongConnect(int x)
{
    dis[x]=ind;
    low[x]=ind++;
    onStack[x]=true;
    S.push(x);

    for(auto i:G[x])
    {
        if(dis[i]==-1)
        {
            strongConnect(i);
            low[x]=min(low[x],low[i]);
        }
        else if(onStack[i])
        {
            low[x]=min(low[x],dis[i]);
        }
    }

    if(dis[x]==low[x])
    {
        cnt+=1;
        do
        {
            topStack=S.top();
            onStack[topStack]=false;
            comp[cnt].push_back(topStack);
            S.pop();
        }
        while(topStack!=x);
    }
}