Cod sursa(job #2925505)

Utilizator kanyjmkSabau Eduard kanyjmk Data 15 octombrie 2022 14:56:04
Problema Componente tare conexe Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.2 kb
#include <iostream>
#include <fstream>
#include <stack>
#include <vector>
using namespace std;

ifstream fin("ctc.in");
ofstream fout("ctc.out");
int id = 1, num_scc = 0;
vector<vector<int>> sccs;
void dfs(int curr_node, int& n, vector<vector<int>>&ad_list, int low_vals[100001], int ids[100001], bool on_stack[100001], stack<int>& scc_stack)
{
    scc_stack.push(curr_node);
    on_stack[curr_node] = true;
    ids[curr_node] = low_vals[curr_node] = id;
    id++;
    for(auto it = ad_list[curr_node].begin(); it < ad_list[curr_node].end(); it++)
    {
        if(ids[*it] == 0)
            {
                dfs(*it, n, ad_list, low_vals, ids, on_stack, scc_stack);
                low_vals[curr_node] = min(low_vals[curr_node], low_vals[*it]);
            }
        else if(on_stack[*it])
                low_vals[curr_node] = min(low_vals[curr_node], low_vals[*it]);
    }
    if(ids[curr_node] == low_vals[curr_node])
        {
            num_scc++;
            vector<int> scc;
            while(curr_node != scc_stack.top())
            {
                int node = scc_stack.top();
                on_stack[node] = false;
                low_vals[node] = ids[curr_node];
                scc.push_back(node);
                scc_stack.pop();
            }while(curr_node != scc_stack.top());

            int node = scc_stack.top();
            on_stack[node] = false;
            low_vals[node] = ids[curr_node];
            scc.push_back(node);
            scc_stack.pop();

            sccs.push_back(scc);
        }
}

int main()
{
    int n, m;
    int low_vals[100001];
    int ids[100001];
    bool on_stack[100001];
    stack<int> scc_stack;

    fin >> n >> m;
    vector<vector<int>>ad_list(n+1);
    for(int i = 1; i <= m; i++)
    {
        int x, y;
        fin >> x >> y;
        ad_list[x].push_back(y);
    }
    for(int i = 1; i <= n; i++)
        if(ids[i] == 0)
            dfs(i, n, ad_list, low_vals, ids, on_stack, scc_stack);
    
    fout << num_scc << '\n';
    for(int i = 0; i < num_scc; i++)
        {
            for(auto j = sccs[i].begin(); j < sccs[i].end(); j++)
                fout << *j << " ";
            fout << '\n';
        }
}