Cod sursa(job #2930156)

Utilizator NefelibataAnton Marius Alexandru Nefelibata Data 27 octombrie 2022 16:49:21
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.79 kb
#include <bits/stdc++.h>
using namespace std;
void dfs(int node, stack<int> &st, vector<int> &vis, vector<int> adj[]) {
    vis[node] = 1;
    for(auto it: adj[node]) {
        if(!vis[it]) {
            dfs(it, st, vis, adj);
        }
    }

    st.push(node); //facem dfs si punem nodurile pe stiva in ordinea in care
                   //ajungem la capete (frunzele din arborele de dfs)
}
void revDfs(int node, vector<int> &vis, vector<int> transpose[]) {
    cout << node << " ";
    vis[node] = 1;
    for(auto it: transpose[node]) {
        if(!vis[it]) {
            revDfs(it, vis, transpose);
        }
    }
}
int main() {
    int n, m, x, y;
    ifstream f("ctc.in");
    f>>n>>m;
	vector<int> adj[n+1];
	for (int i = 0; i < m; ++i) {
        f>>x>>y;
        adj[x].push_back(y); //citirea muchiilor
	}
	stack<int> st; //stiva pe care vom pune nodurile in ordinea precizata mai sus
	vector<int> vis(n+1, 0);
	for(int i = 1;i<=n;i++) {
	    if(!vis[i]) {
	        dfs(i, st, vis, adj); //chemam dfs prima data
	    }
	}
	vector<int> transpose[n+1];
	for(int i = 1;i<=n;i++) {
	    vis[i] = 0;
	    for(auto it: adj[i]) {
	        transpose[it].push_back(i); //facem graful transpus
	    }
	}
	int k = 0;
	while(!st.empty()) {
	    int node = st.top(); //selectam nodul initial drept primul nod de pe stiva
	    st.pop(); //si ii dam pop. repetam pana cand stiva este goala.
	    if(!vis[node]) { //se face dfs inversat doar pentru nodurile nevizitate
	        revDfs(node, vis, transpose); //chemam dfs inversat pentru graful transpus. dfs inversat este de fapt un dfs normal, dar pe graful transpus. nodurile se parcurg invers, si se si printeaza
	        cout << endl;
	        ++k; //incrementam nr de componente tare conexe
	    }
	}
	cout<<k;
	return 0;
}