Pagini recente » Cod sursa (job #1275768) | Cod sursa (job #97300) | Cod sursa (job #1366679) | Cod sursa (job #358693) | Cod sursa (job #527416)
Cod sursa(job #527416)
#include<fstream>
#include<vector>
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
# define nmax 100002
vector <int> v[nmax], vt[nmax],c[nmax];
int N, M, l[nmax], lt[nmax], t[nmax], o[nmax], pas;
bool viz[nmax];
void citire()
{
f>>N>>M;
int a, b;
for(;M;--M)
{
f>>a>>b;
v[a].push_back(b);
vt[b].push_back(a);
}
for(a=1;a<=N;++a)
{
l[a]=v[a].size();
lt[a]=vt[a].size();
}
}
void dfv(int nod)
{
viz[nod]=1; t[nod]=N-pas; pas++;
int k;
for(k=0;k<l[nod];++k)
if(!viz[v[nod][k]]) dfv(v[nod][k]);
}
void dfvt(int nod)
{
viz[nod]=1;
c[pas].push_back(nod);
int k;
for(k=0;k<lt[nod];++k)
if(!viz[vt[nod][k]]) dfvt(vt[nod][k]);
}
int main()
{
citire(); int i, s, j;
for(i=1;i<=N;i++)
if(!viz[i]) dfv(i);
for(i=1;i<=N;i++)
{
o[t[i]]=i; viz[i]=0;
}
pas=0;
for(i=1;i<=N;i++)
if(!viz[o[i]])
{
pas++;
dfvt(o[i]);
}
g<<pas<<'\n';
for(i=1;i<=pas;i++)
{
s=c[i].size();
for(j=0;j<s;j++)
g<<c[i][j]<<' ';
g<<'\n';
}
}