Cod sursa(job #3213289)

Utilizator xbornAvasilcai Andrei-Cristian xborn Data 12 martie 2024 20:44:37
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.6 kb
#include <bits/stdc++.h>
using namespace std;
const int max_node = 1000;
vector<int> graph[max_node];
vector<int> transpose_graph[max_node];
vector<vector<int>>afis(100000);
bool vis[max_node];
int scc_count=0;
vector<int> node_order;
void dfs(int n){
    if(vis[n]) return;
    int len=graph[n].size();
    vis[n]=true;
    for(int i=0;i<len;i++)
        dfs(graph[n][i]);
    node_order.push_back(n);
}
void dfs_print(int n){
    if(vis[n]==true) return;
    afis[scc_count].push_back(n);
    int len=transpose_graph[n].size();
    vis[n]= true;
    for(int i=0;i<len;i++)
        dfs_print(transpose_graph[n][i]);
}
int kosarajuSCC(int n)
{

    for(int i= 1; i<=n; i++)
        if(vis[i] == false)
            dfs(i);
    for(int i= 1; i<=n; i++)
        vis[i]= false;
    for(int i= node_order.size()-1; i>= 1; i--)
    {
        if(vis[node_order[i]] == false)
        {
            dfs_print(node_order[i]);
            scc_count++;
        }
    }
    node_order.clear();
    return scc_count;
}
int main(void)
{
    ifstream fin("ctc.in");
    ofstream fout("ctc.out");
    int n,m,x,y;
    fin>>n>>m;
    for(int i= 0; i<= n; i++)
    {
        vis[i]= false;
        graph[i].clear();
        transpose_graph[i].clear();
    }
    for(int i=0;i<m;i++)
    {
        fin>>x>>y;
        graph[x].push_back(y);
        transpose_graph[y].push_back(x);
    }
    int components=kosarajuSCC(n);
    fout<<components<<'\n';
    for(int i=0;i<scc_count;i++,fout<<'\n')
        for(int j=0;j<afis[i].size();++j)
            fout<<afis[i][j]<<' ';
    return 0;
}