Pagini recente » Cod sursa (job #1280426) | Cod sursa (job #404939) | Cod sursa (job #2801343) | Cod sursa (job #647005) | Cod sursa (job #2477833)
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
const int NMAX=100005;
vector <int> g[2][NMAX];
bool viz[2][NMAX];
int ctc[NMAX];
int n, m, cc;
void RESET()
{
for(int i=0; i<=n+3; i++)
viz[0][i]=viz[1][i]=0;
}
void DFS(int u, int semn)
{
int v;
viz[semn][u]=1;
for(int j=0; j<g[semn][u].size(); j++)
{
v=g[semn][u][j];
if (!viz[semn][v])
DFS(v, semn);
}
}
int CTC()
{
int cc=0;
for(int i=1; i<=n; i++)
{
if (ctc[i]==0)
{
RESET();
cc++;
DFS(i, 0);
DFS(i, 1);
for(int j=1; j<=n; j++)
{
if (viz[0][j]==1 && viz[1][j]==1)
ctc[j]=cc/*, printf("%d ", j)*/;
}
//printf("\n");
}
}
return cc;
}
int main()
{
freopen("ctc.in", "r", stdin);
freopen("ctc.out", "w", stdout);
int u, v, cc, i, j;
scanf("%d%d", &n, &m);
for(i=1; i<=m; i++)
{
scanf("%d%d", &u, &v);
g[0][u].push_back(v);
g[1][v].push_back(u);
}
cc=CTC();
printf("%d\n", cc);
for(j=1; j<=cc; j++)
{
for(i=1; i<=n; i++)
{
if(ctc[i]==j)
printf("%d ", i);
}
printf("\n");
}
return 0;
}