Cod sursa(job #1565435)

Utilizator BugirosRobert Bugiros Data 10 ianuarie 2016 19:17:53
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.89 kb
#include <fstream>
#include <vector>
using namespace std;

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

const int MAXN = 100005;

struct nod
{
    vector<int> vecini;
    int index;
    bool pestiva;
    int vecinminim;
    nod();
};

nod::nod()
{
    index = -1;
    pestiva = false;
    vecinminim = 0;
}

nod v[MAXN];
int n;
int stiva[MAXN];
int l_stiva = 0;
int index = 0;

vector<int> componente[MAXN];
int nr_componente = 0;


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

void conectare_tare(int i)
{
    v[i].index = index;
    v[i].vecinminim = index;
    ++index;
    stiva[++l_stiva] = i;
    v[i].pestiva = true;
    for (unsigned int j = 0;j < v[i].vecini.size();++j)
    {
        int vecin = v[i].vecini[j];
        if (v[vecin].index == -1)
        {
            conectare_tare(vecin);
            v[i].vecinminim = min(v[i].vecinminim, v[vecin].vecinminim);
        }
        else if (v[vecin].pestiva)
        {
            v[i].vecinminim = min(v[i].vecinminim, v[vecin].index);
        }
    }
    if (v[i].vecinminim == v[i].index)
    {
        ++nr_componente;
        int vecin;
        do
        {
            vecin = stiva[l_stiva--];
            v[vecin].pestiva = false;
            componente[nr_componente].push_back(vecin);
        }while(vecin != i);
    }
}


void tarjan()
{
    for (int i = 1;i <= n;++i)
        if (v[i].index == -1)
            conectare_tare(i);
}


void afisare()
{
    out << nr_componente << '\n';
    for (int i = 1;i <= nr_componente;++i)
    {
        for (unsigned int j = 0; j < componente[i].size();++j)
            out << componente[i][j] << ' ';
        out << '\n';
    }
}

int main()
{
    citire();
    tarjan();
    afisare();
    return 0;
}