Pagini recente » Cod sursa (job #2448420) | Cod sursa (job #118696) | Cod sursa (job #2025290) | Cod sursa (job #120642) | Cod sursa (job #1221225)
#include <iostream>
#include <stack>
#include <vector>
#include <utility>
using namespace std;
vector<int> to_print;
int n, m, idx, cnt;
vector<pair<bool, vector<int>>> adj[2]; // 0 - graf normal, 1 graf intors
stack<int> s;
void dfs(int which, int nod){
adj[which][nod].first = true;
for(int i = 0; i < adj[which][nod].second.size(); i++){
if(!adj[which][adj[which][nod].second.at(i)].first){
if(which)
to_print.push_back(adj[which][nod].second.at(i) + 1);
dfs(which, adj[which][nod].second.at(i));
}
}
if(!which)
s.push(nod);
}
int main(){
int a, b;
freopen("ctc.in", "r", stdin);
freopen("ctc.out", "w", stdout);
scanf("%d%d", &n, &m);
vector<int> v;
for(int i = 0; i < n; i++){
adj[0].push_back(make_pair(false, v));
adj[1].push_back(make_pair(false, v));
}
for(int i = 0; i < m; i++){
scanf("%d%d", &a, &b);
adj[0][--a].second.push_back(--b);
adj[1][b].second.push_back(a);
}
for(int i = 0; i < n; i++){
if(!adj[0][i].first){
dfs(0, i);
}
}
while(!s.empty()){
int nod = s.top();
s.pop();
if(!adj[1][nod].first){
dfs(1, nod);
to_print.push_back(nod+1);
to_print.push_back(0);
cnt++;
}
}
printf("%d\n", cnt);
for(int i = 0; i < to_print.size(); i++){
if(!to_print[i])
printf("\n");
else
printf("%d ", to_print[i]);
}
return 0;
}