Cod sursa(job #1167351)

Utilizator tester9x9Tester9x9 tester9x9 Data 4 aprilie 2014 20:20:53
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.63 kb
#include <fstream>
#include <vector>
#include <stack>
#define NM 100010

using namespace std;

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

int N, M, K;
vector<int> G[NM];
int Index[NM], LowLink[NM];
stack<int> Stack;
bool InStack[NM];
vector< vector<int> > Components;

void DF (int node)
{
    Index[node]=LowLink[node]=++K;
    InStack[node]=1;
    Stack.push(node);

    for (vector<int>::iterator it=G[node].begin(); it!=G[node].end(); ++it)
        if (Index[*it]==0)
        {
            DF(*it);
            LowLink[node]=min(LowLink[node], LowLink[*it]);
        }
        else
            if (InStack[*it])
                LowLink[node]=min(LowLink[node], Index[*it]);

    if (LowLink[node]>=Index[node])
    {
        vector<int> Aux;

        for (; !Stack.empty() && Stack.top()!=node; InStack[Stack.top()]=0, Stack.pop())
            Aux.push_back(Stack.top());

        if (!Stack.empty() && Stack.top()==node)
        {
            Aux.push_back(Stack.top());
            InStack[Stack.top()]=0;
            Stack.pop();
        }

        Components.push_back(Aux);
    }
}

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

    for (int i=1; i<=N; i++)
        if (Index[i]==0)
            DF(i);

    g << Components.size() << '\n';
    for (size_t i=0; i<Components.size(); i++)
    {
        for (vector<int>::iterator it=Components[i].begin(); it!=Components[i].end(); ++it)
            g << (*it) << ' ';
        g << '\n';
    }

    f.close();
    g.close();

    return 0;
}