Cod sursa(job #1495727)

Utilizator DiClauDan Claudiu DiClau Data 3 octombrie 2015 15:39:21
Problema Componente tare conexe Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.82 kb
#include<stdio.h>
using namespace std;
const int N = 100001, M = 200002;
int vf[M], urm[M], lst[N], nr = 0, v[N], c, rez[M], c2, x2[M*2], y2[M*2];
bool viz[N];
void adauga(int x, int y)
{
    nr++;
    vf[nr] = y;
    urm[nr] = lst[x];
    lst[x] = nr;
}
void dfs1 (int x)
{
    int p, y;
    p = lst[x];
    viz[x] = true;
    while (p != 0)
    {
        y = vf[p];
        if (viz[y] == false)
        {
            dfs1(y);
            v[++c] = y;
        }
        p = urm[p];
    }
}
void dfs2 (int x)
{
    int p, y;
    p = lst[x];
    viz[x] = true;
    rez[++c2] = x;
    while (p != 0)
    {
        y = vf[p];
        if (viz[y] == false)
            dfs2(y);
        p = urm[p];
    }
}
int main ()
{
    FILE *in, *out;
    in = fopen ("ctc.in", "r");
    out = fopen ("ctc.out", "w");
    int n, m;
    fscanf (in, "%d%d", &n, &m);
    int i, x, y;
    for (i = 1; i <= m; i++)
    {
        fscanf (in, "%d%d", &x, &y);
        x2[i] = x;
        y2[i] = y;
        adauga (x, y);
    }
    for (i = 1; i <= n; i++)
        if (viz[i] == 0)
        {
            dfs1(i);
            v[++c] = i;
        }
    for (i = 1; i <= n; i++)
    {
        lst[i] = 0;
        viz[i] = false;
    }
    for (i = 1; i <= m; i++)
    {
        vf[i] = 0;
        urm[i] = 0;
    }
    for (i = 1; i <= m; i++)
        adauga(y2[i], x2[i]);
    int comp = 0;
    for (i = n; i >= 1; i--)
        if (viz[v[i]] == 0)
        {
            comp++;
            dfs2(v[i]);
            rez[++c2] = -1;
        }
    fprintf (out, "%d\n", comp);
    c = 1;
    for (i = 1; i <= comp; i++)
    {
        while (rez[c] != -1)
        {
            fprintf (out, "%d ", rez[c]);
            c++;
        }
        c++;
        fprintf (out, "\n");
    }
    return 0;
}