Pagini recente » Cod sursa (job #2199262) | Cod sursa (job #933996) | Cod sursa (job #735473) | Cod sursa (job #2834299) | Cod sursa (job #2757241)
#include <cstdio>
#include <vector>
#include <stack>
#include <bitset>
using namespace std;
vector<vector<int>> G, Gt, components;
bitset<100005> used;
stack<int> s;
void DFS(int k) {
used[k] = true;
for (auto v: G[k])
if(!used[v])
DFS(v);
s.push(k);
}
void DFST(int k) {
used[k] = true;
components.back().emplace_back(k);
for (auto v: Gt[k])
if (!used[v])
DFST(v);
}
int main()
{
freopen("ctc.in", "r", stdin);
freopen("ctc.out", "w", stdout);
int N, M;
scanf("%d%d", &N, &M);
G.resize(N + 1);
Gt.resize(N + 1);
int from, to;
for (int i = 0; i <= M; ++i) {
scanf("%d%d", &from, &to);
G[from].emplace_back(to);
Gt[to].emplace_back(from);
}
for (int i = 1; i <= N; ++i)
if (!used[i])
DFS(i);
used = 0;
while (!s.empty()) {
from = s.top();
s.pop();
if (used[from]) continue;
components.emplace_back(vector<int>());
DFST(from);
}
printf("%d\n", (int)components.size());
for (auto c: components) {
for (auto v: c)
printf("%d ", v);
printf("\n");
}
return 0;
}