Cod sursa(job #2743898)

Utilizator MateGMGozner Mate MateGM Data 23 aprilie 2021 17:27:40
Problema Componente tare conexe Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.57 kb
#include <iostream>
#include <fstream>
#include <stack>
#include <vector>
using namespace std;

ifstream be("ctc.in");
ofstream ki("ctc.out");

void dfs_scc(vector<vector<int>>& adj, vector<int>& b, vector<bool>& vis, vector<int>& low, stack<int>& st, vector<vector<int>>& comp, int& com, int& t, int v) {

    t++;
    b[v] = t;
    low[v] = t;
    vis[v] = true;
    st.push(v);
    for (auto i : adj[v]) {

        if (b[i] == -1) {

            dfs_scc(adj, b, vis, low, st, comp, com, t, i);
            low[v] = min(low[v], low[i]);
        }
        else if ((b[i] < b[v]) && vis[i]) {
            low[v] = min(low[v], b[i]);
        }
    }
    if (low[v] == b[v]) {
        com++;
        comp.resize(com);
        while (!st.empty() && (b[st.top()] >= b[v])) {
            comp[com - 1].push_back(st.top());
            vis[st.top()] = false;
            st.pop();
        }
    }
}

void tarjan(vector<vector<int> > &adj,int n)
{
    vector<int>b(n,-1);
    vector<bool>vis(n,false);
    vector<int>low(n,-1);
    stack<int>st;
    vector<vector<int> >comp;
    int t=0;
    int com=0;
    for(int i=0;i<n;i++)
        if(b[i]==-1)
            dfs_scc(adj, b, vis, low, st, comp, com, t, i);
    ki<<com<<endl;
    for(int i=comp.size()-1;i>=0;i--)
    {
        for(int j=comp[i].size()-1;j>=0;j--){
            ki << comp[i][j] + 1 << " ";
        }
        ki<<endl;
    }
}

int main()
{

    int n,m;
    be>>n>>m;
    vector<vector<int> > adj(n+1);
    for(int i=0;i<m;i++)
    {
        int x,y;
        be>>x>>y;
        adj[x-1].push_back(y-1);
    }
    tarjan(adj,n);
    return 0;
}