Cod sursa(job #1922337)

Utilizator AlexBlagescuBlagescu Alex George AlexBlagescu Data 10 martie 2017 17:02:51
Problema Componente tare conexe Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.1 kb
#include <fstream>
#include <stack>
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
int n,index,m,i,nr,a[101][101],viz[101],pes[101],ll[101];
int sol[101][101],k[101];
stack <int> S;
void tc(int v)
{   viz[v]=index;
    ll[v]=index;
    index++;
    S.push(v);
    pes[v]=1;
    for(int j=1;j<=n;j++)
    {   if(!viz[j] and a[v][j])
        {
            tc(j);
            ll[v]=min(ll[v],ll[j]);
        }
        else if(pes[j] and a[v][j])
                ll[v]=min(ll[v],viz[j]);
    }
    if(ll[v]==viz[v])
    {   nr++;
        int w;
        do
        {   w=S.top();
            sol[nr][++k[nr]]=w;
            S.pop();
            pes[w]=0;
        }
        while(w!=v);
    }
}
void tarjan()
{   index=0;
    for(i=1;i<=n;i++)
        if(!viz[i]) {tc(i);}
}
int main()
{   f>>n>>m;
    for(i=1;i<=m;i++)
    {   int u,v;
        f>>u>>v;
        a[u][v]=1;
    }
    tarjan();
    g<<nr<<'\n';
    for (i=1;i<=nr;i++)
    {
        for (int j=1;j<=k[i];j++)
            g<<sol[i][j]<<' ';
        g<<'\n';
    }
    g.close();
    return 0;
}