Cod sursa(job #2871543)

Utilizator Botzki17Botocan Cristian-Alexandru Botzki17 Data 15 martie 2022 00:37:06
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.64 kb
#include <bits/stdc++.h>
#include <fstream>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");

#define ll long long
const int NMAX = 100000;

vector<int>g[NMAX+5];
int low_link[NMAX+5], ids[NMAX+5];
bitset<NMAX+5>in_stack;
stack<int> st;
vector< vector<int> >strong_components;
int index;




void dfs_tarjan(int node){
    st.push(node);
    in_stack[node] = 1;
    ids[node] = index;
    low_link[node] = index;
    index++;

    for(int i =0; i < g[node].size(); i++){
        int x = g[node][i];
        if(ids[x] == 0)
            dfs_tarjan(x);
        if(in_stack[x])
             low_link[node] = min(low_link[node], low_link[x]);

    }

    if(ids[node] == low_link[node]){
        vector<int> strong_component;
        int x = -1;
        do{
            x = st.top();
            in_stack[x] = 0;
            low_link[x] = ids[node];
            strong_component.push_back(x);
            st.pop();

        }
        while(x != node);
        strong_components.push_back(strong_component);
    }
}

void tarjan(int n){
    index = 1;
    int scc = 0;
    for(int i =1; i <=n; i++)
    {
        if(ids[i] == 0){
            dfs_tarjan(i);
        }
    }
}


int main(){
    int n, m, x, y;
    fin>>n>>m;
    for(int i =1; i <=m; i++){
        fin>>x>>y;
        g[x].push_back(y);
    }
    tarjan(n);
    fout<<strong_components.size()<<"\n";
    for(int i =0 ; i < strong_components.size(); i++)
    {
        for(int j =0; j < strong_components[i].size(); j++)
            fout<<strong_components[i][j]<<" ";
        fout<<"\n";
    }




    return 0;
}