Cod sursa(job #3002748)

Utilizator tomaionutIDorando tomaionut Data 15 martie 2023 08:27:26
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.14 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("ctc.in");
ofstream fout("ctc.out");

int n, m, st[100005], top, nr;
bitset <100005> viz;
vector <int> a[100005], t[100005], scc[100005];

void Dfs(int x)
{
    viz[x] = 1;
    for (int i = 0; i < a[x].size(); i++)
        if (viz[a[x][i]] == 0)
        Dfs(a[x][i]);
    st[++top] = x;
}

void Dfs2(int x)
{
    viz[x] = 0;
    for (int i = 0; i < t[x].size(); i++)
        if (viz[t[x][i]] == 1)
        Dfs2(t[x][i]);
    scc[nr].push_back(x);
}

int main()
{
    int i, x, y;
    fin >> n >> m;
    for (i = 1; i <= m; i++)
    {
        fin >> x >> y;
        a[x].push_back(y);
        t[y].push_back(x);
    }

    for (i = 1; i <= n; i++)
        if (viz[i] == 0)
        Dfs(i);

    for (i = n; i >= 1; i--)
        if (viz[st[i]] == 1)
        {
            nr++;
            Dfs2(st[i]);
        }

    fout << nr << "\n";
    for (i = 1; i <= nr; i++)
    {
        sort(scc[i].begin(), scc[i].end());
        for (int j = 0; j < scc[i].size(); j++)
            fout << scc[i][j] << " ";
        fout << "\n";
    }
    return 0;
}