Cod sursa(job #2489269)

Utilizator vladcainamisirVlad Cainamisir vladcainamisir Data 8 noiembrie 2019 11:27:04
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.27 kb
#include<cstdio>
#include<vector>
using namespace std;
const int NMAX = 100000;
vector<int>v[NMAX + 1];
vector<int>pred[NMAX + 1];
vector<int>v2;
vector<int>mat[NMAX + 1];
bool viz[NMAX + 1];
void dfs(int nod)
{
    viz[nod] = 1;
    for(int i = 0 ; i < v[nod].size() ; i ++)
    {
        if(viz[v[nod][i]] == 0)
            dfs(v[nod][i]);
    }
    v2.push_back(nod);
}
void dfs2(int nod ,int lin)
{
    viz[nod] = 1;
    for(int i = 0 ; i < pred[nod].size() ; i ++)
    {
        if(viz[pred[nod][i]] == 0)
            dfs2(pred[nod][i] , lin);
    }
    mat[lin].push_back(nod);

}
int main()
{
int n , m , x , y;
    freopen("ctc.in" , "r" , stdin);
    freopen("ctc.out" , "w" , stdout);
    scanf("%d%d" , &n , &m);
    for(int i = 1; i <= m ; i ++)
    {
        scanf("%d%d" , &x, &y);
        v[x].push_back(y);
        pred[y].push_back(x);
    }
    for(int i = 1; i <= n ; i ++)
        if(viz[i] == 0)
            dfs(i);
    for(int i = 0; i <= n ; i ++)
        viz[i] = 0;
    int k = 0;
    for(int i = n - 1; i >= 0 ; i --)
    {

        if(viz[v2[i]] == 0)
        dfs2(v2[i] , ++k);

    }
    printf("%d\n" , k);
    for(int i = 1; i <= k ; i ++){
        for(int j = 0 ; j < mat[i].size() ; j ++)
        printf("%d " , mat[i][j]);
    printf("\n");
    }
    return 0;
}