Cod sursa(job #3121975)

Utilizator AlexMariMarinescu Alexandru AlexMari Data 16 aprilie 2023 16:30:13
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.57 kb
#include<bits/stdc++.h>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");

int n, m, vis[100005];
vector<int>g[100005];
vector<int>rev[100005];
vector<int>components[100005];

int stack_finish_time[100005];

int nr_elem;

int nr_strongly_components;

void dfs(int node)
{
    vis[node] = 1;
    for (int i = 0; i < g[node].size(); i++)
        if (vis[g[node][i]] == 0)
            dfs(g[node][i]);

    stack_finish_time[++nr_elem] = node;
}


void dfs_inv(int node)
{
    vis[node] = 1;
    for (int i = 0; i < rev[node].size(); i++)
        if (vis[rev[node][i]] == 0)
        dfs_inv(rev[node][i]);

    components[nr_strongly_components].push_back(node);
}



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

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

    for (int i = 1; i <= n; i++)
        vis[i] = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < g[i].size(); j++)
            rev[g[i][j]].push_back(i);
    }


    for (int i = nr_elem; i >= 1; i--) {
        if (vis[stack_finish_time[i]] == 0) {
            nr_strongly_components++;
            dfs_inv(stack_finish_time[i]);
        }

    }

    fout << nr_strongly_components << '\n';
    for (int i = 1; i <= nr_strongly_components; i++) {
        for (int j = 0; j < components[i].size(); j++)
            fout << components[i][j] << " ";
        fout << '\n';
    }

    return 0;
}