Pagini recente » Cod sursa (job #3130385) | Cod sursa (job #1878576) | Istoria paginii runda/preoli10/clasament | Monitorul de evaluare | Cod sursa (job #1515656)
#include <iostream>
#include <fstream>
using namespace std;
bool boolbreak,viz[10000],a[10000][10000],t[10000][10000];
unsigned short v[10000],i,j,k,n,m,x,y,q,grup[10000];
ifstream f("ctc.in");
ofstream g("ctc.out");
void read()
{
f>>n>>m;
for(i=1;i<=m;i++)
{
f>>x>>y;
a[x][y]=1;
t[y][x]=1;
}
}
void deep_search(int i, bool m[][10000])
{
v[1]=i; k=1; m[0][i]=1;
do
{
boolbreak=0;
for(j=1;j<=n;j++)
{
if (m[v[k]][j] && !m[0][j] && grup[j]==0)
{
v[++k]=j;
m[0][j]=1;
boolbreak=1;
}
if (boolbreak) break;
}
if(j>n) --k;
}while(k>0);
}
void write()
{
g<<q<<endl;
for(i=1;i<=n;i++)
{
if (!viz[grup[i]])
{
viz[grup[i]]=1;
for (j=i;j<=n;j++)
if(grup[j]==grup[i])
g<<j<<" ";
g<<endl;
}
}
}
int main()
{
read();
for(i=1;i<=n;i++)
if(grup[i]==0)
{
deep_search(i,a);
deep_search(i,t);
++q;
for(j=1;j<=n;j++)
if(a[0][j] && t[0][j] && grup[j]==0)
grup[j]=q;
for(j=1;j<=n;j++)
{
a[0][j]=0;
t[0][j]=0;
}
}
write();
g.close();
return 0;
}