Pagini recente » Cod sursa (job #554981) | Cod sursa (job #2754173) | Cod sursa (job #1887458) | Cod sursa (job #169017) | Cod sursa (job #1536579)
#include <iostream>
#include <fstream>
#include <string.h>
#include <vector>
#include <stack>
using namespace std;
const int nmax = 100003;
vector <int> G[nmax], invG[nmax];
int k,n,len;
int visited[nmax],result[nmax];
stack <int> S;
void Melysegi(int ind);
void MelysegiInv(int ind);
int main(){
int m, a, b;
freopen("ctc.in", "r", stdin);
freopen("ctc.out", "w", stdout);
scanf("%d %d", &n, &m);
for (; m--;) {
scanf("%d %d", &a, &b);
G[a].push_back(b);
invG[b].push_back(a);
}
memset(visited, 0, 4 * (n + 2));
// KUsaraju
for (int i = 1; i <= n; i++) {
if (visited[i] == 0) Melysegi(i);
}
memset(visited, 0, 4 * (n + 2));
memset(result, -1, 4 * (n + 2));
k = 0; len = 0;
while (!S.empty()) {
if (visited[S.top()] == 0) {
k++;
MelysegiInv(S.top());
}
S.pop();
}
// done
printf("%d", k);
k = 0;
for (int i = 0; i < len; i++) {
if (visited[result[i]] == k) printf(" %d", result[i]);
else { printf("\n%d", result[i]); k++; }
}
fclose(stdout);
fclose(stdin);
return 0;
}
void Melysegi(int ind) {
visited[ind] = 1;
for (int j = 0; j < G[ind].size(); j++) {
if (visited[G[ind][j]] == 0) Melysegi(G[ind][j]);
}
S.push(ind);
}
void MelysegiInv(int ind) {
visited[ind] = k;
result[len++] = ind;
for (int j = 0; j < invG[ind].size(); j++) {
if (visited[invG[ind][j]] == 0) MelysegiInv(invG[ind][j]);
}
}