Pagini recente » Cod sursa (job #2950534) | Cod sursa (job #317023) | Cod sursa (job #890120) | Cod sursa (job #1563667) | Cod sursa (job #2931655)
/*
Aplic algoritmul lui Kosaraju, folosind proprietatea unei componente tare conexe ca daca inversez muchiile din aceasta, va ramane componenta tare conexa.
Parcurg graful initial cu un dfs si adaug un nod in stiva dupa ce parcurg toti vecinii lui.
Parcurg graful cu muchiile inversate cu un dfs din nodurile pop-uite din stiva, pe rand, si actualizez evident vectorul de vizitare.
Este esential sa introduc in stiva nodul DUPA ce parcurg toti vecinii lui, ca apoi cand parcurg dfs pe graful cu muchiile inversate sa incep din el, si sa vad daca pot ajunge inapoi prin muchiile prin care am ajuns la nodul respectiv
O(n+m)
*/
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream cin("ctc.in");
ofstream cout("ctc.out");
int n,m,current;
vector<vector<int>> graph;
vector<vector<int>> reversedGraph;
vector<vector<int>> solution;
vector<bool> viz;
stack<int> s;
void initializeViz(){
for(int i=1;i<=n;++i)
viz[i]=false;
}
void dfs(int node){
for(int i=0;i<graph[node].size();++i){
if(!viz[graph[node][i]]){
viz[graph[node][i]]=true;
dfs(graph[node][i]);
}
}
s.push(node);
}
void reverseDfs(int node){
solution[current].push_back(node);
viz[node]=true;
for(int i=0;i<reversedGraph[node].size();++i){
if(!viz[reversedGraph[node][i]]){
reverseDfs(reversedGraph[node][i]);
}
}
}
int main()
{
int i,a,b,top;
cin>>n>>m;
graph.resize(n+1);
reversedGraph.resize(n+1);
viz.resize(n+1);
for(i=0;i<m;++i){
cin>>a>>b;
graph[a].push_back(b);
reversedGraph[b].push_back(a);
}
initializeViz();
for(i=1;i<=n;++i){
if(!viz[i]){
dfs(i);
}
}
initializeViz();
while(!s.empty()){
top=s.top();
s.pop();
if(!viz[top]){
solution.push_back({});
reverseDfs(top);
current++;
}
}
cout<<current<<'\n';
for(i=0;i<current;++i){
for(int j=0;j<solution[i].size();++j){
cout<<solution[i][j]<<' ';
}
cout<<'\n';
}
return 0;
}