Cod sursa(job #3214776)

Utilizator MerlinTheWizardMelvin Abibula MerlinTheWizard Data 14 martie 2024 13:55:13
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.29 kb
#include<bits/stdc++.h>
#pragma GCC optimize("O3")

using namespace std;

const int NMAX = 2e5 + 5;
int n, m;
vector<int> v[NMAX], inv[NMAX], top, culoare[NMAX];
bool viz[NMAX];

void dfs_top(int node)
{
    viz[node] = true;

    for(auto u : inv[node])
        if(!viz[u])
            dfs_top(u);
    top.push_back(node);
}

void dfs(int node, int col)
{
    culoare[col].push_back(node);
    viz[node] = true;

    for(auto u : v[node])
        if(!viz[u])
            dfs(u, col);

}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    freopen("ctc.in", "r", stdin);
    freopen("ctc.out", "w", stdout);

    int a, b;
    cin >> n >> m;
    for(int i = 1; i <= m; i++)
    {
        cin >> a >> b;
        v[a].push_back(b);
        inv[b].push_back(a);
    }

    for(int i = 1; i <= n; i++)
        if(!viz[i])
            dfs_top(i);
        
    int col = 0;
    memset(viz, 0, sizeof(viz));
    for(int i = top.size() - 1; i >= 0; i--)
    {
        if(!viz[top[i]])
        {
            col++;
            dfs(top[i], col);
        }
    }

    cout << col << "\n";

    for(int i = 1; i <= col; i++)
    {
        for(auto u : culoare[i])
            cout << u << " ";
        cout << "\n";
    }
}