Cod sursa(job #1583968)

Utilizator dorin31Geman Dorin Andrei dorin31 Data 29 ianuarie 2016 16:18:27
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.41 kb
#include <iostream>
#include <fstream>
#include <vector>

#define maxN 100001

using namespace std;

ifstream fin("ctc.in");
ofstream fout("ctc.out");

int n,m;
vector <int> v[maxN];
vector < vector <int> > ctc;
bool inQ[maxN];
int idx[maxN], lowlink[maxN], st[maxN];

void citire()
{
    int x,y;
    fin>>n>>m;
    for (int i=1; i<=m; ++i)
    {
        fin>>x>>y;
        v[x].push_back(y);
    }
}

int minim(int a, int b)
{
    if (a<b) return a;
    return b;
}

void Tarjan(int x)
{
    st[++st[0]]=x;
    inQ[x]=true;

    idx[x]=++idx[0];
    lowlink[x]=idx[0];

    for (int i=0; i<v[x].size(); ++i)
    {
        if (!idx[v[x][i]]) Tarjan(v[x][i]);
        if (inQ[v[x][i]])
            lowlink[x] = minim(lowlink[x], lowlink[v[x][i]]);
    }

    if (idx[x]==lowlink[x])
    {
        ctc.push_back(vector <int>());
        while (st[st[0]]!=x)
        {
            ctc.back().push_back(st[st[0]]);
            inQ[st[st[0]]]=false;
            --st[0];
        }
        ctc.back().push_back(x);
        inQ[x]=false;
        --st[0];
    }
}


int main()
{
    citire();
    for (int i=1; i<=n; ++i)
        if (!idx[i]) Tarjan(i);
    fout<<ctc.size()<<'\n';
    for (int i=0; i<ctc.size(); ++i)
    {
        for (vector <int>::iterator it=ctc[i].begin(); it!=ctc[i].end(); ++it)
            fout<<*it<<' ';
        fout<<'\n';
    }
    return 0;
}