Pagini recente » Cod sursa (job #2729108) | Cod sursa (job #926298) | Cod sursa (job #673160) | Cod sursa (job #2433410) | Cod sursa (job #1427878)
#include <iostream>
#include <vector>
#include <list>
using namespace std;
const int NMAX = 100000;
struct {
vector<int> vecini;
bool vizitat = false;
} graf[NMAX], grafT[NMAX];
list<int> fin;
vector<int> results[NMAX];
void dfs(int v) {
graf[v].vizitat = true;
for (const int u: graf[v].vecini) {
if (!graf[u].vizitat) {
dfs(u);
}
}
fin.push_front(v);
}
void dfsT(int v, int comp) {
grafT[v].vizitat = true;
for (const int u: grafT[v].vecini) {
if (!grafT[u].vizitat) {
dfsT(u, comp);
}
}
results[comp].push_back(v);
}
int main() {
freopen("ctc.in", "r", stdin);
freopen("ctc.out", "w", stdout);
int N, M; scanf("%d %d\n", &N, &M);
while (M--) {
int v, u; scanf("%d %d\n", &v, &u);
graf[v].vecini.push_back(u);
grafT[u].vecini.push_back(v);
}
for (int v = 1; v <= N; v++) {
if (!graf[v].vizitat) {
dfs(v);
}
}
int comp = 0;
for (const int v: fin) {
if (!grafT[v].vizitat) {
dfsT(v, comp++);
}
}
printf("%d\n", comp);
while (comp--) {
for (const int v: results[comp]) {
printf("%d ", v);
}
printf("\n");
}
return 0;
}