Pagini recente » Cod sursa (job #2266798) | Cod sursa (job #2357434) | Cod sursa (job #2695088) | Cod sursa (job #476168) | Cod sursa (job #630257)
Cod sursa(job #630257)
#include<cstdio>
#include<vector>
using namespace std;
int n, m;
vector <int> LGraf[100001], LGrafInv[100001], S[100001];
int viz1[100001], viz2[100001];
inline void DF(int k, vector <int> *L, int *viz)
{
unsigned int i;
viz[k] = 1;
for(i = 0; i < L[k].size(); i++)
if(viz[L[k][i]] == 0) {
viz[L[k][i]] = 1;
DF(L[k][i], L, viz);
}
}
int main() {
int i, j, x, y, nr;
freopen("ctc.in", "r", stdin), freopen("ctc.out", "w", stdout);
scanf("%d %d", &n, &m);
for(i = 1; i <= m; i++) {
scanf("%d %d", &x, &y);
LGraf[x].push_back(y);
LGrafInv[y].push_back(x);
}
nr = 0;
for(i = 1; i <= n; i++) {
if(viz1[i] == 0) {
DF(i, LGraf, viz1);
DF(i, LGrafInv, viz2);
bool inc = false;
for(j = 1; j <= n; j++)
if(viz1[j] == 1 && viz2[j] == 1) {
viz1[j] = viz2[j] = 2;
if(!inc) { nr++; inc = true; }
S[nr].push_back(j);
}
else if(viz1[j] == 1 || viz2[j] == 1) viz1[j] = viz2[j] = 0;
}
}
printf("%d\n", nr);
for(i = 1; i <= nr; i++) {
for(j = 0; j < S[i].size(); j++)
printf("%d ", S[i][j]);
printf("\n");
}
return 0;
}