Cod sursa(job #2166429)

Utilizator eduardvintilaVintila Eduard eduardvintila Data 13 martie 2018 17:04:13
Problema Componente tare conexe Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.25 kb
#include <bits/stdc++.h>

using namespace std;

int pre[100005],lowlink[100005],idx,n,nr=0;

vector<int> v[100005],comp;
vector< vector<int> > ctc;
stack<int> stiva;

void dfs(int i)
{
    pre[i]=idx;
    lowlink[i]=idx;
    idx++;
    stiva.push(i);
    for (size_t k=0;k<v[i].size();k++)
    {
        int j=v[i][k];
        if (pre[j]==-1)
            dfs(j);
        lowlink[i]=min(lowlink[i],lowlink[j]);
    }
    if (lowlink[i]==pre[i])
    {
        while (true)
        {
            int x=stiva.top();
            stiva.pop();
            pre[x]=nr;
            lowlink[x]=n;
            comp.emplace_back(x);
            if (x==i)
                break;
        }
        nr++;
        ctc.emplace_back(comp);
        comp.clear();
    }
}

int main()
{
    ifstream f("ctc.in");
    ofstream g("ctc.out");
    int m,i,y,x,j;
    f>>n>>m;
    for (i=1;i<=m;i++)
    {
        f>>x>>y;
        v[x].emplace_back(y);
    }
    for (i=1;i<=n;i++)
        pre[i]=-1;
    for (i=1;i<=n;i++)
    {
        if (pre[i]==-1)
            dfs(i);
    }
    g<<nr<<endl;
    for (i=0;i<nr;i++)
    {
        for (j=ctc[i].size()-1;j>=0;j--)
            g<<ctc[i][j]<<" ";
        g<<endl;
    }
    return 0;
}