Cod sursa(job #787477)

Utilizator tzipleatudTudor Tiplea tzipleatud Data 13 septembrie 2012 14:27:31
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.47 kb
#include <fstream>
#include <vector>
#include <stack>
#define NM 100010

using namespace std;

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

int N,M,i,j;
int K;
int a,b;
vector<int> G[NM];
vector<int> ANS[NM];
stack<int> S;
int NCTC;
int Lev[NM],MinLev[NM];
bool InS[NM];

void DoTarjan (int nod)
{
    Lev[nod]=MinLev[nod]=++K;
    S.push(nod);
    InS[nod]=1;

    int nnod;
    for (vector<int>::iterator it=G[nod].begin(); it!=G[nod].end(); it++)
    {
        nnod=*it;
        if (!Lev[nnod])
        {
            DoTarjan(nnod);
            MinLev[nod]=min(MinLev[nod],MinLev[nnod]);
            continue;
        }
        MinLev[nod]=min(MinLev[nod],MinLev[nnod]);
    }

    if (Lev[nod]==MinLev[nod])
    {
        ++NCTC;

        while (!S.empty() && S.top()!=nod)
        {
            InS[S.top()]=0;
            ANS[NCTC].push_back(S.top());
            S.pop();
        }
        if (!S.empty())
        {
            InS[S.top()]=0;
            ANS[NCTC].push_back(S.top());
            S.pop();
        }
    }
}

int main ()
{
    f >> N >> M;
    for (i=1; i<=M; i++)
    {
        f >> a >> b;
        G[a].push_back(b);
    }

    for (i=1; i<=N; i++)
        if (!Lev[i])
            DoTarjan(i);

    g << NCTC << '\n';
    for (i=1; i<=NCTC; i++)
    {
        for (j=0; j<ANS[i].size(); j++)
            g << ANS[i][j] << ' ';
        g << '\n';
    }

    f.close();
    g.close();
    return 0;
}