Cod sursa(job #2792445)

Utilizator realmeabefirhuja petru realmeabefir Data 1 noiembrie 2021 18:01:18
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.41 kb
#include <iostream>
#include <bits/stdc++.h>

using namespace std;

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

int n,m;
vector<int> la[100005];
vector<int> lat[100005];
int viz1[100005];
int viz2[100005];

vector<int> topo;
int cc = 0;
vector<int> comp[100005];

void dfs1(int s)
{
    viz1[s] = 1;
    for (auto nod: la[s])
    {
        if (!viz1[nod])
            dfs1(nod);
    }
    topo.push_back(s);
}

void dfs2(int s)
{
    viz2[s] = 1;
    comp[cc].push_back(s);
    for (auto nod: lat[s])
    {
        if (!viz2[nod])
            dfs2(nod);
    }
}

int main()
{
    f >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int x,y;
        f >> x >> y;
        la[x].push_back(y);
        lat[y].push_back(x);
    }

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

    reverse(topo.begin(), topo.end());

    for (auto i: topo)
    {
        if (!viz2[i])
        {
            cc++;
            dfs2(i);
        }
    }

    g << cc << '\n';
    /*
    for (int i = 1; i <= cc; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            if (comp[j] == i)
                g << j << ' ';
        }
        g << '\n';
    }*/
    for (int i = 1; i <= cc; i++)
    {
        for (auto el: comp[i])
            g << el << ' ';
        g << '\n';
    }

    return 0;
}