Cod sursa(job #1895208)

Utilizator patrutoiuandreipatrutoiu andrei patrutoiuandrei Data 27 februarie 2017 20:37:21
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.42 kb
#include <fstream>
#include <vector>

#define Ndim 100001
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int index,nrctc,Q[Ndim];
bool VIZ[Ndim];
struct vertex{int index,lowlink;bool inQ;}V[Ndim];
vector <int> G[Ndim],CTC[Ndim];
void StrongConnect(int nod)
{
    VIZ[nod] = 1;
    V[nod].index = index;
    V[nod].lowlink = index;
    index++;
    Q[++Q[0]] = nod;
    V[nod].inQ = true;
    for(size_t i=0;i<G[nod].size();i++)
    {
        int fiu = G[nod][i];
        if(VIZ[fiu]==0)
        {
            StrongConnect(fiu);
            V[nod].lowlink = min(V[nod].lowlink, V[fiu].lowlink);
        }
        else if(V[fiu].inQ == true)
        {
            V[nod].lowlink = min(V[nod].lowlink, V[fiu].lowlink);
        }
    }
    int x;
    if(V[nod].index == V[nod].lowlink)
    {
        nrctc++;
        do
        {
            x = Q[Q[0]];
            Q[0]--;
            CTC[nrctc].push_back(x);
            V[x].inQ = false;
        }while(x!=nod);
    }
}
int main()
{
    int n,m,i,a,b,j;
    fin>>n>>m;
    for(i=1;i<=m;i++)
    {
        fin>>a>>b;
        G[a].push_back(b);
    }
    for(i=1;i<=n;i++)
    {
        if(VIZ[i]==0)
        {
            StrongConnect(i);
        }
    }
    fout<<nrctc<<'\n';
    for(i=1;i<=nrctc;i++,fout<<'\n')
    {
        for(j=0;j<CTC[i].size();j++)
            fout<<CTC[i][j]<<' ';
    }
    return 0;
}