Cod sursa(job #2082716)

Utilizator filip.mihalutMihalut Filip filip.mihalut Data 6 decembrie 2017 18:45:37
Problema Componente tare conexe Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.29 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(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;
}