Pagini recente » Cod sursa (job #1105225) | Cod sursa (job #1942442) | Cod sursa (job #2240659) | Cod sursa (job #952635) | Cod sursa (job #2925294)
#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;
}