Cod sursa(job #3287187)

Utilizator Simon2712Simon Slanina Simon2712 Data 16 martie 2025 19:57:59
Problema Componente tare conexe Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.65 kb
#include <fstream>
#include <stack>
#include <vector>
#include <algorithm>

using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
const int N = 1e5;
vector<int> graph[N + 1];
int n, m;
void read(){
    fin>>n>>m;
    for(int i = 1; i <= m; i++)
    {
        int x, y;
        fin>>x>>y;
        graph[x].push_back(y);
    }
}
int currtime = 0;
int scc_cnt = 0;
struct node{
    int t_in, low;
    bool on_stack;
}nodes[N + 1];
vector<int> sccs[N + 1];
stack<int> st;
void create_scc(int head)
{
    scc_cnt++;
    while(st.top()!=head)
    {
        int x = st.top();
        st.pop();
        sccs[scc_cnt].push_back(x);
    }
    st.pop();
    sccs[scc_cnt].push_back(head);
}

void dfs(int x){
    currtime++;
    nodes[x].t_in = nodes[x].low = currtime;
    nodes[x].on_stack = true;
    st.push(x);
    for(int y:graph[x])
    {
        if(!nodes[y].t_in)
        {
            dfs(y);
            nodes[x].low = min(nodes[x].low, nodes[y].low);
        }
        else
        if(nodes[y].on_stack)///we found an edge that climbs back up
            nodes[x].low = min(nodes[x].low, nodes[y].t_in);
    }
    if(nodes[x].low == nodes[x].t_in)///no one from under x climbs higher than x -> the subtree( which we can recreate from stack by going till x ) is an scc
        create_scc(x);
}
void find_sccs(){ ///scc = strongly connected component
    for(int i = 1; i <= n; i++)
        if(!nodes[i].t_in)
            dfs(i);
}
void answerin(){
    fout<<scc_cnt<<'\n';
    for(int i = 1; i <= scc_cnt; i++)
    {
        for(int j:sccs[i])
            fout<<j<<' ';
        fout<<'\n';
    }
}
int main()
{
    read();
    find_sccs();
    answerin();
    return 0;
}