Cod sursa(job #1363216)

Utilizator supermitelArdelean Razvan Mitel supermitel Data 26 februarie 2015 19:59:26
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.53 kb
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <bitset>
#include <vector>

using namespace std;

int n;
vector<int> vec1[100010];
vector<int> vec2[100010];
vector<int> postfix;
vector<vector<int> > sol;

bitset<100010> viz1;
bitset<100010> viz2;

void dfs1(int x)
{
    if(viz1[x])
        return;
    viz1[x] = 1;
    for(int i = 0; i < vec1[x].size(); i++)
        dfs1(vec1[x][i]);
    postfix.push_back(x);
}

void dfs2(int x, vector<int> & v)
{
    if(viz1[x] == 0 || viz2[x])
        return;
    viz2[x] = 1;
    for(int i = 0; i < vec2[x].size(); i++)
        dfs2(vec2[x][i], v);
    v.push_back(x);
}

void citire()
{
    int m, x, y;
    scanf("%d%d", &n, &m);
    for(int i = 0; i < m; i++)
    {
        scanf("%d%d", &x, &y);
        vec1[x].push_back(y);
        vec2[y].push_back(x);
    }
}

void solve()
{
    for(int i = 1; i <= n; i++)
        if(!viz1[i])
            dfs1(i);
    reverse(postfix.begin(), postfix.end());
    for(int i = 0; i < n; i++)
        if(!viz2[postfix[i]])
    {
        vector<int> nou;
        dfs2(postfix[i], nou);
        sol.push_back(nou);
    }
}

void afisare()
{
    printf("%d\n", sol.size());
    for(int i = 0; i < sol.size(); i++)
    {
        for(int j = 0; j < sol[i].size(); j++)
            printf("%d ", sol[i][j]);
        printf("\n");
    }

}

int main()
{
    freopen("ctc.in", "r", stdin);
    freopen("ctc.out", "w", stdout);

    citire();
    solve();
    afisare();

    return 0;
}