Pagini recente » Cod sursa (job #2343237) | Cod sursa (job #272119) | Cod sursa (job #1968816) | Cod sursa (job #123972) | Cod sursa (job #1089641)
#include <fstream>
#include <cstring>
#include <vector>
using namespace std;
const int N = 1 + 1e5;
vector<int> graph[N], trans[N];
int stack[N];
bool use[N];
ifstream in("ctc.in");
ofstream out("ctc.out");
void dfs(vector<int>* graph, int x, void (*work)(int)){
use[x] = true;
for (vector<int> :: iterator it = graph[x].begin() ; it != graph[x].end() ; it++)
if (!use[*it])
dfs(graph, *it, work);
work(x);
}
void addToStack(int x){
stack[ ++stack[0] ] = x;
}
void print(int x){
out << x << ' ';
}
void doNothing(int x){}
int main(){
int n, m, x, y;
in >> n >> m;
while (m--){
in >> x >> y;
graph[x].push_back(y);
trans[y].push_back(x);
}
memset(use, false, sizeof(use));
for (int i = 1 ; i <= n ; i++)
if (!use[i])
dfs(trans, i, addToStack);
memset(use, false, sizeof(use));
int ans = 0;
while (stack[0]){
x = stack[ stack[0]-- ];
if (!use[x]){
dfs(graph, x, doNothing);
ans++;
}
}
out << ans << "\n";
stack[0] = n;
memset(use, false, sizeof(use));
while (stack[0]){
x = stack[ stack[0]-- ];
if (!use[x]){
dfs(graph, x, print);
out << '\n';
}
}
return 0;
}