Cod sursa(job #2082732)

Utilizator filip.mihalutMihalut Filip filip.mihalut Data 6 decembrie 2017 18:58:00
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.31 kb
#include <bits/stdc++.h>
#define dim  100002

using namespace std;

ifstream f ("ctc.in");
ofstream g ("ctc.out");

vector < int > v1[dim];
vector < int > v2[dim];
vector < int > v3[dim];
int n,m,i,j,x,y,seen[dim], vec[dim], k;

void read()
{
    f >> n >> m;

    for(int i = 1; i <= m; i++)
    {
        f >> x >> y;
        v1[x].push_back(y);
        v2[y].push_back(x);
    }
}

void dfs1(int x)
{
    seen[x] = 1;
    int l = v2[x].size(), next_x;
    for(int i = 0; i < l; i++)
    {
        next_x = v2[x][i];
        if(not seen[next_x])
            dfs1(next_x);
    }
    vec[++k] = x;
}

void dfs2(int x)
{
    seen[x] = -1;
    int l = v1[x].size(), next_x;
    for(int i = 0; i < l; i++)
    {
        next_x = v1[x][i];
        if(seen[next_x] != -1)
            dfs2(next_x);
    }
    v3[k].push_back(x);
}

int main()
{
    read();

    for(int i = 1; i <= n; i++)
        if(not seen[i])
            dfs1(i);

    k = 0;
    for(int i = n; i >= 1; i--)
        if(seen[vec[i]] != -1)
        {
            k++;
            dfs2(vec[i]);
        }

    g << k << '\n';

    for(int i = 1; i <= k; i++)
    {
        int l = v3[i].size();
        for(int j = 0; j < l; j++)
            g << v3[i][j] << " ";
        g << '\n';
    }
    return 0;
}