Pagini recente » Cod sursa (job #1303683) | Cod sursa (job #2035733) | Cod sursa (job #1894715) | Cod sursa (job #3349811) | Cod sursa (job #3309087)
#include<iostream>
#include<fstream>
#include<vector>
using namespace std;
ifstream in("ctc.in");
ofstream out("ctc.out");
vector<vector<int>> graph;
vector<vector<int>> tgraph;
vector<bool> visited;
int n, m;
void read(){
in>>n>>m;
graph.resize(n);
tgraph.resize(n);
visited.resize(n);
int a, b;
for (int i=0;i<m;i++){
in>>a>>b;
graph[a-1].push_back(b-1);
tgraph[b-1].push_back(a-1);
}
}
void dfs1(int node, vector<int>& topological) {
visited[node] = true;
for(int k: graph[node]) {
if (!visited[k]) {
dfs1(k, topological);
}
}
topological.push_back(node);
}
void dfs2(int node, vector<int>&comp){
comp.push_back(node);
visited[node] = true;
for(int k: tgraph[node]) {
if (!visited[k]) {
dfs2(k, comp);
}
}
}
void solve() {
vector<int> topological;
for (int i=0;i<n;i++){
if(!visited[i]) {
dfs1(i, topological);
}
}
visited = vector<bool>(n, false);
vector<vector<int>> components;
for(auto iter = topological.rbegin(); iter!=topological.rend(); iter++){
int here = *iter;
if (!visited[here]) {
vector<int> component;
dfs2(here, component);
components.push_back(move(component));
}
}
out<<components.size()<<endl;
for(const auto&c: components) {
for(int node: c){
out<<node+1<<" ";
}
out<<'\n';
}
}
int main(){
read();
solve();
return 0;
}