Pagini recente » Cod sursa (job #1390537) | Statistici gaz pirce (gazpirce) | Istoria paginii runda/pre004/clasament | Cod sursa (job #329519) | Cod sursa (job #1834347)
#include <fstream>
#include <cstdio>
#include <vector>
#define VAL 100005
using namespace std;
int N, M, i, j;
int x, y, K;
int gasit[VAL];
int ok[VAL], ok2[VAL];
vector<int> G[VAL];
vector<int> Ginv[VAL];
vector<int> comp[VAL];
vector<int> :: iterator it;
void dfs(int x, vector<int> Graf[], int gas[], int pas)
{
vector<int> :: iterator it;
gas[x]=K;
if (pas==2 && ok[x]==K)
gasit[x]=K;
for (it=Graf[x].begin(); it!=Graf[x].end(); it++)
if (gas[*it]<K)
dfs(*it, Graf, gas, pas);
}
int main()
{
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);
G[x].push_back(y);
Ginv[y].push_back(x);
}
for (i=1; i<=N; i++)
{
if (gasit[i]==0)
{
++K;
gasit[i]=K;
comp[K].push_back(i);
ok[i]=K;
dfs(i, G, ok, 1);
ok2[i]=K;
dfs(i, Ginv, ok2, 2);
}
else
comp[gasit[i]].push_back(i);
}
printf("%d\n", K);
for (i=1; i<=K; i++)
{
for (it=comp[i].begin(); it!=comp[i].end(); it++)
printf("%d ", *it);
printf("\n");
}
return 0;
}