Pagini recente » Cod sursa (job #1159091) | Cod sursa (job #162690) | Cod sursa (job #2844740) | Cod sursa (job #223045) | Cod sursa (job #3221331)
#include <iostream>
#include <fstream>
#include <stdint.h>
#include <vector>
const int32_t MAX_N = 100000;
std::vector<int32_t> adj[MAX_N];
std::vector<int32_t> adjt[MAX_N];
int32_t used[MAX_N];
int32_t sort[MAX_N], top;
std::vector<int32_t> comps[MAX_N];
int32_t compTop = 0;
void SortDFS(int32_t node) {
used[node] = 1;
for(int32_t next : adjt[node])
if(!used[next])
SortDFS(next);
sort[top++] = node;
}
void PlusDFS(int32_t node) {
used[node] = 1;
comps[compTop].push_back(node);
for(int32_t next : adj[node])
if(!used[next])
PlusDFS(next);
}
void MinusDFS(int32_t node) {
used[node] = 2;
for(int32_t next : adjt[node])
if(used[next] == 1)
MinusDFS(next);
}
int main() {
std::ifstream fin("ctc.in");
std::ofstream fout("ctc.out");
int32_t n, m;
fin >> n >> m;
for(int32_t i = 0; i != m; ++i) {
int32_t x, y;
fin >> x >> y;
--x; --y;
adj[x].push_back(y);
adjt[y].push_back(x);
}
for(int32_t i = 0; i != n; ++i) {
if(!used[i])
SortDFS(i);
}
for(int32_t i = 0; i != n; ++i)
used[i] = 0;
while(--top != -1) {
if(used[sort[top]])
continue;
PlusDFS(sort[top]);
MinusDFS(sort[top]);
++compTop;
}
fout << compTop << '\n';
for(int32_t i = 0; i != compTop; ++i) {
for(int32_t node : comps[i])
fout << (node + 1) << ' ';
fout << '\n';
}
fin.close();
fout.close();
return 0;
}