Pagini recente » Cod sursa (job #567570) | Cod sursa (job #1558278) | Cod sursa (job #1049193) | Cod sursa (job #1560850) | Cod sursa (job #2920713)
#include <bits/stdc++.h>
using namespace std;
void dfs(int node, int& level, vector<int>& initialLevel, vector<int>& minLevel,
stack<int>& st, vector<bool>& isInStack,
vector<vector<int>>& ctc, vector<vector<int>>& G){
if(minLevel[node] >= 0){
return;
}
level += 1;
initialLevel[node] = level;
minLevel[node] = level;
st.push(node);
isInStack[node] = true;
for(int child: G[node]){
dfs(child, level, initialLevel, minLevel, st, isInStack, ctc, G);
if(isInStack[child]){
minLevel[node] = min(minLevel[node], minLevel[child]);
}
}
if(initialLevel[node] == minLevel[node]){
ctc.push_back({});
int x = -1;
do{
x = st.top();
st.pop();
isInStack[x] = false;
ctc.back().push_back(x);
}while(x != node);
}
}
int main(){
ifstream cin("ctc.in");
ofstream cout("ctc.out");
int N, M;
cin >> N >> M;
vector<vector<int>> G(N + 1);
int x, y;
for(int i = 1; i <= M; ++i){
cin >> x >> y;
G[x].push_back(y);
}
int level = 0;
vector<int> initialLevel(N + 1, -1);
vector<int> minLevel(N + 1, -1);
stack<int> st;
vector<bool> isInStack(N + 1, false);
vector<vector<int>> ctc;
for(int node = 1; node <= N; ++node){
if(minLevel[node] < 0){
dfs(node, level, initialLevel, minLevel, st, isInStack, ctc, G);
}
}
cout << ctc.size() << "\n";
for(vector<int>& nodes: ctc){
for(int node: nodes){
cout << node << " ";
}
cout << "\n";
}
cin.close();
cout.close();
return 0;
}