Cod sursa(job #1261760)

Utilizator IonSebastianIon Sebastian IonSebastian Data 12 noiembrie 2014 17:45:46
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.51 kb
#include <fstream>
#include <vector>
using namespace std;

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

const int MAX_N = 100000, MAX_M = 200000;

int lst1[MAX_N+1], urm1[MAX_M+1], vf1[MAX_M+1];
int lst2[MAX_N+1], urm2[MAX_M+1], vf2[MAX_M+1];
int nr1, nr2;

int nrcomp;
vector<int> comp[MAX_N+1];
int n, m;

void add(int x, int y)
{
    nr1++;
    urm1[nr1] = lst1[x];
    lst1[x] = nr1;
    vf1[nr1] = y;
    nr2++;
    urm2[nr2] = lst2[y];
    lst2[y] = nr2;
    vf2[nr2] = x;
}

int st[MAX_N+1];
int nre;

bool viz[MAX_N+1];

void dfs1(int x)
{
    int p = lst1[x];
    viz[x] = true;
    while(p != 0)
    {
        if(!viz[vf1[p]])
            dfs1(vf1[p]);
        p = urm1[p];
    }
    st[++nre] = x;
}

void dfs2(int x, int k)
{
    int p = lst2[x];
    viz[x] = false;
    while(p != 0)
    {
        if(viz[vf2[p]])
        {
            dfs2(vf2[p], k);
            comp[k].push_back(vf2[p]);
        }
        p = urm2[p];
    }
}

int main()
{
    in >> n >> m;

    int i, x, y;

    for(i = 0; i < m; i++)
    {
        in >> x >> y;
        add(x,y);
    }

    for(i = 1; i <= n; i++)
    {
        if(!viz[i])
            dfs1(i);
    }
    while(nre != 0){
        if(viz[st[nre]])
        {
            dfs2(st[nre],++nrcomp);
            comp[nrcomp].push_back(st[nre]);
        }
        nre--;
    }
    out << nrcomp << "\n";
    for(i = 1; i <= nrcomp; i++)
    {
        for(int j = 0; j < comp[i].size(); j++)
        {
            out << comp[i][j] << " ";
        }
        out << "\n";
    }
    return 0;
}