Cod sursa(job #1131395)

Utilizator tzipleatudTudor Tiplea tzipleatud Data 28 februarie 2014 19:54:42
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.48 kb
#include <fstream>
#include <stack>
#include <vector>
#include <algorithm>
#define NM 100010

using namespace std;

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

int N, M, K, NR;
vector<int> G[NM];
vector<int> Component[NM];
int Level[NM], LowLink[NM];
bool In[NM];
stack<int> S;

void DoTarjan (int node)
{
    Level[node]=LowLink[node]=++K;
    S.push(node);
    In[node]=1;

    for (vector<int>::iterator it=G[node].begin(); it!=G[node].end(); ++it)
    {
        if (!Level[*it])
            DoTarjan(*it);

        if (In[*it])
            LowLink[node]=min(LowLink[node], LowLink[*it]);
    }

    if (LowLink[node]==Level[node])
    {
        ++NR;
        for (; !S.empty() && S.top()!=node; S.pop())
        {
            Component[NR].push_back(S.top());
            In[S.top()]=0;
        }
        if (!S.empty() && S.top()==node)
        {
            Component[NR].push_back(S.top());
            In[S.top()]=0;
            S.pop();
        }
    }
}

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 (!Level[i])
            DoTarjan(i);

    g << NR << '\n';
    for (int i=1; i<=NR; i++)
    {
        for (vector<int>::iterator it=Component[i].begin(); it!=Component[i].end(); ++it)
            g << (*it) << ' ';

        g << '\n';
    }

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

    return 0;
}