Cod sursa(job #2998420)

Utilizator TanasaStefanTanasa Stefan TanasaStefan Data 9 martie 2023 14:10:32
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.21 kb
#include <bits/stdc++.h>

using namespace std;

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

int n , m , comp;

vector < int > v[100005] , vt[100005] , sol[100005];

stack < int > st;

int used[100005];

void dfs(int nod)
{
    used[nod] = 1;

    for (auto i : v[nod])
    {
        if(!used[i])
        {
            dfs(i);
        }
    }
    st . push(nod);
}

void dfs1(int nod)
{
    sol[comp] . push_back(nod);
    used[nod] = 2;

    for (auto i : vt[nod])
    {
        if(used[i] != 2)
        {
            dfs1(i);
        }
    }
}

int main()
{
    f >> n >> m;

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

    for ( int i = 1 ; i <= n ; i++)
    {
        if(!used[i])
        dfs(i);
    }

    while(!st . empty())
    {
        if(used[st . top()] != 2)
        {
            comp++;
            dfs1(st . top());
        }
        st . pop();
    }

     g << comp << '\n';

     for ( int i = 1 ; i <= comp ; i++)
     {
         for ( auto x : sol[i])
            g << x << " ";

         g << '\n';
     }

     return 0;
}