Pagini recente » Cod sursa (job #3201549) | Cod sursa (job #1355514) | Cod sursa (job #1221383) | Cod sursa (job #861684) | Cod sursa (job #2935464)
#include <bits/stdc++.h>
#include <fstream>
using namespace std;
vector<vector<int>> graph;
vector<vector<int>> graph_t;
int index;
stack <int> st;
vector<int> viz;
vector<vector<int>> comp;
void DFS_t(vector<vector<int>> graph_t, int n, int x, int index){
viz[x]=index;
for(int i=0;i<graph_t[x].size();i++){
if(viz[graph_t[x][i]]==0){
DFS_t(graph_t,n,graph_t[x][i], index);
}
}
st.push(x);
}
void DFS(vector<vector<int>> graph, int n, int x){
viz[x]=index;
for(int i=0;i<graph[x].size();i++){
if(viz[graph[x][i]]==0){
DFS(graph,n,graph[x][i]);
}
}
st.push(x);
}
int main() {
index=1;
int n,m;
ifstream f;
ofstream g;
f.open("graf.in");
g.open("graf.out");
f>>n>>m;
graph.resize(n+1);
graph_t.resize(n+1);
viz.resize(n+1);
for(int i=0;i<m;i++){
int x,y;
f>>x>>y;
graph[x].push_back(y);
graph_t[y].push_back(x);
}
// Kosaraju
for(int i=1;i<=n;i++){
if(viz[i]==0){
DFS(graph,n,i);
}
}
for(int i=1;i<=n;i++){
viz[i]=0;
}
while(st.size()){
int x=st.top();
st.pop();
if(viz[x]==0){
DFS_t(graph_t, n, x, index);
vector<int>arr;
for(int i=1;i<=n;i++){
if(viz[i]==index){
arr.push_back(i);
}
}
index+=1;
comp.push_back(arr);
}
}
g<<index-1<<"\n";
for(auto & i : comp){
for(int j : i){
g<<j<<" ";
}
g<<"\n";
}
return 0;
}