Cod sursa(job #3226566)

Utilizator GargantuanRoOprea Rares GargantuanRo Data 21 aprilie 2024 23:34:03
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.47 kb
#include <fstream>
#include <vector>
#include <stack>
using namespace std;

ifstream cin("ctc.in");
ofstream cout("ctc.out");

const int nmax = 2e5 + 7;
vector <int> adj[nmax];
vector <int> cc[nmax];
stack<int>s;
int low[nmax], id[nmax], on_stack[nmax];
int curent_id = 0, ssc = 0;

void dfs(int node)
{
    curent_id++;
    id[node] = curent_id;
    s.push(curent_id);
    on_stack[curent_id] = 1;
    for(auto next:adj[node])
    {
        if(id[next] == 0)
            dfs(next);
        if(on_stack[id[next]] == 1)
            low[id[node]] = min(low[id[node]], low[id[next]]);
    }
    if(id[node] == low[id[node]] && on_stack[id[node]] == 1)
    {
        while(id[node] != s.top())
        {
            low[s.top()] = id[node];
            on_stack[s.top()] = 0;
            s.pop();
        }
        on_stack[s.top()] = 0;
        s.pop();
        ssc++;
    }
}

int main()
{
    int n,m,i;
    cin >> n >> m;
    for(i = 1; i <= m; i++)
    {
        int a, b;
        cin >> a >> b;
        adj[a].push_back(b);
    }
    for(i = 1; i <= n; i++)
        low[i] = i;
    for(i = 1; i <= n; i++)
        if(id[i] == 0)
            dfs(i);
    cout << ssc << endl;
    for(i = 1; i <= n; i++)
        cc[low[id[i]]].push_back(i);
    for(i = 1; i < nmax; i++)
    {
        if(cc[i].size())
        {
            for(auto it:cc[i])
                cout << it << " ";
            cout << endl;
        }
    }
    return 0;
}