Pagini recente » Cod sursa (job #2055975) | Cod sursa (job #1569935) | Cod sursa (job #814829) | Cod sursa (job #646501) | Cod sursa (job #1179442)
#include<fstream>
#include<vector>
#include<bitset>
#define Next (++pos==100)?(fin.read(Buffer,100),pos = 0):0
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int n,m,pos,str;
vector<int>vin[100005];
vector<int>pleaca[100005];
vector<int>componente[100005];
bitset<100005>viza;
bitset<100005>vizb;
bitset<100005>viz;
char Buffer[100];
inline void Read(int &x)
{
while(Buffer[pos]<'0' || '9'<Buffer[pos])
Next;
x = 0;
while('0'<=Buffer[pos] && Buffer[pos]<='9')
{
x = x*10 +Buffer[pos]-'0';
Next;
}
}
inline void Citire()
{
int i,x,y;
fin.read(Buffer,100);
Read(n);Read(m);
for (i=1;i<=m;i++)
{
Read(x);Read(y);
pleaca[x].push_back(y);
vin[y].push_back(x);
}
}
inline void DFSa(int x)
{
int i,len;
viza[x]=1;
len=pleaca[x].size();
for (i=0;i<len;i++)
if (!viza[pleaca[x][i]])
DFSa(pleaca[x][i]);
}
inline void DFSb(int x)
{
int i,len;
vizb[x]=1;
len=vin[x].size();
for (i=0;i<len;i++)
if (!vizb[vin[x][i]])
DFSb(vin[x][i]);
}
inline void Rezolva()
{
int i,j;
for (i=1;i<=n;i++)
if (!viz[i])
{
for (j=1;j<=n;j++)
viza[j]=vizb[j]=0;
DFSa(i);
DFSb(i);
str++;
for (j=1;j<=n;j++)
if (viza[j] && vizb[j])
{
viz[j]=1;
componente[str].push_back(j);
}
}
}
inline void Afisare()
{
int i,j;
fout<<str<<"\n";
for (i=1;i<=str;i++)
{
for (j=0;j<componente[i].size();j++)
fout<<componente[i][j]<<" ";
fout<<"\n";
}
}
int main()
{
Citire();
Rezolva();
Afisare();
return 0;
}