Cod sursa(job #2298404)

Utilizator victorv88Veltan Victor victorv88 Data 8 decembrie 2018 09:46:31
Problema Componente tare conexe Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.23 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>

using namespace std;

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

vector<int>graph[100005];
vector<int>inversat[100005];
vector<int>sol[100000];
stack<int>s;
int n,m, from, to, viz[100005], viz_invers[100005],k=0;

void dfs(int ind)
{
    viz[ind]=1;
    for (auto &v:graph[ind])
    {
        if (viz[v]==0)
        {
            dfs(v);
        }
    }
    s.push(ind);
}

void dfs_invers(int ind)
{
    viz_invers[ind]=1;
    for (auto &v:inversat[ind])
    {
        if (viz_invers[v]==0)
         dfs_invers(v);
    }
    sol[k].push_back(ind);
}

int main() {
    f >> n >> m;
    for (int i=1; i<=m; i++)
    {
        f >> from >> to;
        graph[from].push_back(to);
        inversat[to].push_back(from);
    }
    for (int i=1; i<=n; i++)
    {
        if (viz[i]==0)
        {
            dfs(i);
        }
    }
    while (!s.empty())
    {
        int element=s.top();
        s.pop();
        if (viz_invers[element]==0)
        {
            dfs_invers(element);
            k++;
        }
    }
    g << k <<'\n';
    for (int i=0; i<k; i++)
    {
        for (auto &v:sol[i])
        {
            cout << v <<' ';
        }
        g <<'\n';
    }
    return 0;
}