Pagini recente » Cod sursa (job #2861289) | Cod sursa (job #1837235) | Cod sursa (job #1362258) | Cod sursa (job #880867) | Cod sursa (job #2930156)
#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;
}