Cod sursa(job #2981349)

Utilizator 100pCiornei Stefan 100p Data 17 februarie 2023 19:47:15
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.32 kb
#include <bits/stdc++.h>

#define MAX 100000

using namespace std;

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

int a, b, conect, n, m;
vector<int> ans[MAX + 5];
stack<int> s;
vector<bool> check(MAX + 5);

vector <int> v[MAX + 5], v2[MAX + 5];

void dfs(int x)
{
    check[x] = 1;
    for(auto i : v[x])
    {
        if(!check[i])
            dfs(i);
    }
    s.push(x);
}

void dfs2(int x, int cnx)
{
    check[x] = 1;
    ans[cnx].push_back(x);
    for(auto i : v2[x])
    {
        if(!check[i])
            dfs2(i, cnx);
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    fin >> n >> m;
    for(int i = 1; i <= m; ++i)
    {
        fin >> a >> b;
        v[a].push_back(b);
        v2[b].push_back(a);
    }

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

    fill(check.begin(), check.end(), false);

    while(!s.empty())
    {
        if(!check[s.top()])
        {
            conect++;
            dfs2(s.top(), conect);
        }
        s.pop();
    }

    fout << conect << '\n';
    for(int i = 1;i <= conect; ++i)
    {
        sort(ans[i].begin(), ans[i].end());
        for(auto j : ans[i])
            fout << j << ' ';
        fout << '\n';
    }

    fin.close(), fout.close();
    return 0;
}