Cod sursa(job #1529451)

Utilizator redcrocodileIlies Andreea redcrocodile Data 20 noiembrie 2015 22:04:47
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.16 kb
#include <fstream>
#include <stack>
#include <vector>
using namespace std;

ifstream f("ctc.in");
ofstream g("ctc.out");

stack<int> S;
vector<int> V[100001],G[100001];
int n,m,i,viz[100001],da[100001],mic[100001],nr[100001],numar,k,j;

void ctc(int nod)
{
   int vecin;
   nr[nod] = mic [nod] = numar;
   numar++;
   da[nod] = 1;
   S.push(nod); viz[nod]=1;
   for (size_t i=0; i<G[nod].size(); i++)
   {
       vecin = G[nod][i];
       if (viz[vecin]==0)
        {ctc(vecin); if(mic[nod]>mic[vecin]) mic[nod] = mic[vecin];}
       else if (da[vecin]) { if(mic[nod]>nr[vecin]) mic[nod] = nr[vecin];}
   }
   if (mic[nod] == nr[nod])
   {
       int nn; k++;
        do {
            V[k].push_back(nn = S.top());
            S.pop();
            da[nn] = 0;
        }
        while (nn != nod);
   }
}

int main()
{
    int a,b;
    f>>n>>m;
    for (i=1;i<=m;i++)
    {
        f>>a>>b;
        G[a].push_back(b);
    }
    for (i=1;i<=n;i++)
        if (!viz[i]) ctc(i);
    g<<k<<"\n";
    for (i=1;i<=k;i++)
    {
       for(size_t j=0; j<V[i].size(); j++)
        g<<V[i][j]<<" ";
       g<<"\n";
    }
    return 0;
}