Cod sursa(job #1465767)

Utilizator akaprosAna Kapros akapros Data 27 iulie 2015 22:49:15
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.54 kb
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#define Nmax 100002
using namespace std;
int n, m, i, j, f[Nmax], c;
vector < int > V[Nmax], W[Nmax], C[Nmax];
bool viz[Nmax];
void read()
{
    int x, y;
    freopen("ctc.in", "r", stdin);
    freopen("ctc.out", "w", stdout);
    scanf("%d %d", &n, &m);
    for (i = 1;i <= m; ++ i)
    {
        scanf("%d %d", &x, &y);
        V[x].push_back(y);
        W[y].push_back(x);
    }
}
void dfs(int x)
{
    int i, l = V[x].size();
    for (i = 0; i < l; ++ i)
        if (!viz[V[x][i]])
    {
        viz[V[x][i]] = 1;
        dfs(V[x][i]);
    }
    f[++ f[0]] = x;
}
void DFS(int x)
{
    int i, l = W[x].size();
    for (i = 0; i < l; ++ i)
        if (!viz[W[x][i]])
    {
        viz[W[x][i]] = 1;
        C[c].push_back(W[x][i]);
        DFS(W[x][i]);
    }
}
void solve()
{
    for (i = 1; i <= n; ++ i)
        if (!viz[i])
        {
            viz[i] = 1;
            dfs(i);
        }
    for (i = 0; i <= n; ++ i)
        viz[i] = 0;
    for (i = n; i >= 1; -- i)
        if (!viz[f[i]])
           {
               viz[f[i]] = 1;
               C[c].push_back(f[i]);
               DFS(f[i]);
               ++ c;
           }
}
void write()
{
    int l;
    printf("%d\n", c);
    for (i = 0; i < c; ++ i)
    {
        l = C[i].size();
        for (j = 0; j < l; ++ j)
            printf("%d ", C[i][j]);
        printf("\n");
    }
}
int main()
{
    read();
    solve();
    write();
    return 0;
}