Cod sursa(job #1262551)

Utilizator DiClauDan Claudiu DiClau Data 13 noiembrie 2014 12:12:45
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.54 kb
#include<stdio.h>
using namespace std;
const int L = 200000, N = 100000;
int urm[L], rez[L], v[L], vf[L], lst[N], urm2[L], vf2[L], lst2[N], nr = 0, nr2=0, ct1 = 0, ct2 = 0;
bool viz[L*2];
FILE *in, *out;
void adauga1(int x, int y)
{
    vf[++nr] = y;
    urm[nr] = lst[x];
    lst[x] = nr;
}

void adauga2(int x, int y)
{
    vf2[++nr2] = y;
    urm2[nr2] = lst2[x];
    lst2[x] = nr2;
}
void dfs (int x)
{
    int p, y;
    viz[x] = true;
    p = lst[x];
    while (p != 0)
    {
        y = vf[p];
        if (!viz[y])
            dfs(y);
        p = urm[p];
    }
    v[++ct1] = x;
}
void dfs2 (int x)
{
    int p, y;
    viz[x] = true;
    p = lst2[x];
    rez[++ct2] = x;
    while (p != 0)
    {
        y = vf2[p];
        if (!viz[y])
        {
            dfs2(y);
        }
        p = urm2[p];
    }
}


int main ()
{
    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);
        adauga1(x,y);
        adauga2(y,x);
    }
    int ct = 0;
    for (i = 1; i <= n; i++)
        if (viz[i] == 0)
            dfs(i);
    for (i = 1; i <= n; i++)
        viz[i] = 0;
    for (i = n; i >= 1; i--)
        if (viz[v[i]] == 0){
            dfs2(v[i]);
            rez[++ct2] = -1;
            ct++;
        }

    i = 1;
    fprintf(out, "%d\n", ct);
    while (rez[i] != 0)
    {
        if (rez[i] == -1)
            fprintf(out, "\n");
        else
            fprintf(out, "%d ", rez[i]);
        i++;
    }

    return 0;
}