Cod sursa(job #3207303)

Utilizator TeddyDinutaDinuta Eduard Stefan TeddyDinuta Data 25 februarie 2024 19:46:36
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.26 kb
#include <bits/stdc++.h>

using namespace std;
ifstream in("ctc.in");
ofstream out("ctc.out");
int n, m;
int vis[100005];
vector<int> comp[100005];
stack<int> st;
int x, y;
int c;

void dfs(int node, vector<vector<int>>& adj, int t) {

    vis[node] = c;
    for (auto it : adj[node]) {
        if (vis[it] == 0) {
            dfs(it, adj, t);
        }
    }

    if (t == 0) {
        st.push(node);
    }
}

int main()
{
    in >> n >> m;
    vector<vector<int>> adj(n + 1, vector<int>());
    vector<vector<int>> adjt(n + 1, vector<int>());

    for (int i = 0; i < m; i++) {
        in >> x >> y;
        adj[x].push_back(y);
        adjt[y].push_back(x);
    }

    c = 1;
    for (int i = 1; i <= n; i++) {
        if (vis[i] == 0) {
            dfs(i, adj, 0);
        }
    }

    for (int i = 1; i <= n; i++)
        vis[i] = 0;

    c = 0;
    while (!st.empty()) {
        int node = st.top();
        if (vis[node] == 0) {
            c++;
            dfs(node, adjt, 1);
        }

        comp[vis[node]].push_back(node);
        st.pop();
    }

    out << c << '\n';
    for (int i = 1; i <= c; i++) {
        for (auto it : comp[i])
            out << it << " ";
        out << '\n';
    }
    return 0;
}