Pagini recente » Cod sursa (job #2423127) | Cod sursa (job #2089733) | Cod sursa (job #2378364) | Cod sursa (job #1102410) | Cod sursa (job #266806)
Cod sursa(job #266806)
#include <stdio.h>
#include <queue>
using namespace std;
#define N 100001
#define M 200001
struct muchie { int x, y; };
int *a[N], *at[N];
int vec_a[N], vec_at[N];
int n, m;
muchie vm[M];
int s[N], p[N];
int ncc = 0;
queue<int> coada;
void citeste_graf()
{
scanf("%d%d", &n, &m);
int i, nodX, nodY;
for(i=0;i<m;++i)
{
scanf("%d%d", &nodX, &nodY);
vm[i].x = nodX;
vm[i].y = nodY;
vec_a[nodX]++;
vec_at[nodY]++;
}
for(i=1;i<=n;++i)
{
a[i] = new int[vec_a[i]+1];
at[i] = new int[vec_at[i]+1];
a[i][0] = 0;
at[i][0] = 0;
}
for(i=0;i<m;++i)
{
nodX = vm[i].x;
nodY = vm[i].y;
a[nodX][++a[nodX][0]] = nodY;
at[nodY][++at[nodY][0]] = nodX;
}
}
void breadth_first_1(int start)
{
int e, i;
coada.push(start);
s[start] = ncc;
while(!coada.empty())
{
e = coada.front();
coada.pop();
for(i=1;i<=a[e][0];++i)
{
if(!s[a[e][i]])
{
s[a[e][i]] = ncc;
coada.push(a[e][i]);
}
}
}
}
void breadth_first_2(int start)
{
int e, i;
coada.push(start);
p[start] = ncc;
while(!coada.empty())
{
e = coada.front();
coada.pop();
for(i=1;i<=at[e][0];++i)
{
if(!p[at[e][i]])
{
p[at[e][i]] = ncc;
coada.push(at[e][i]);
}
}
}
}
int main()
{
freopen("ctc.in", "r", stdin);
freopen("ctc.out", "w", stdout);
citeste_graf();
int i, j;
for(i=1;i<=n;++i)
{
if(s[i] == 0)
{
++ncc;
breadth_first_1(i);
breadth_first_2(i);
for(j=1;j<=n;++j) if(s[j]!=p[j]) s[j]=p[j]=0;
}
}
printf("%d\n", ncc);
for(i=1;i<=ncc;++i)
{
for(j=1;j<=n;++j) if(s[j] == i) printf("%d ", j);
printf("\n");
}
fclose(stdin);
return 0;
}