Pagini recente » Cod sursa (job #361137) | Cod sursa (job #932799) | Cod sursa (job #2300134) | Cod sursa (job #1867662) | Cod sursa (job #711143)
Cod sursa(job #711143)
#include<fstream>
#include<vector>
using namespace std;
#define lung 100001
ifstream fin("ctc.in");
ofstream fout("ctc.out");
vector <int> v[lung];
vector <int> transp[lung];
vector <int> rasp[lung];
int i,a,b,n,m,nr,timp[lung],ordine[lung],trecut[lung];
bool viz1[lung],viz[lung];
inline void df(int x)
{int i,p=transp[x].size(),max1=0,val;
if (v[x].size() != 0 && transp[x].size() != 0)
{ for (i=0;i<p;++i)
if (!viz1[transp[x][i]])
if (v[transp[x][i]].size() != 0 && transp[transp[x][i]].size() != 0)
{ viz1[transp[x][i]] = true;
rasp[nr].push_back(transp[x][i]);
df(transp[x][i]);
}
}
}
inline void final(int x)
{int i,p=v[x].size();
timp[++a] = x;
for (i=0;i<p;++i)
if (!viz[v[x][i]])
{ viz[v[x][i]] = true;
final(v[x][i]);
}
}
int main()
{ fin >> n >> m;
for (i=1;i<=m;++i)
{ fin >> a >> b;
v[a].push_back(b);
transp[b].push_back(a);
}
a = 0;
for (i=1;i<=n;++i)
if (!viz[i])
{ viz[i] = true;
final(i);
}
for (i=1;i<=n;++i)
{ trecut[timp[i]] = a;
--a;
}
for (i=1;i<=n;++i)
ordine[n-trecut[i]+1] = i;
for (i=1;i<=n;++i)
if (!viz1[ordine[i]])
{ int k=ordine[i];
++nr;
viz1[k] = true;
rasp[nr].push_back(k);
df(k);
}
fout << nr << '\n';
int j,p;
for (i=1;i<=nr;++i)
{ p=rasp[i].size();
for (j=0;j<p;++j)
fout << rasp[i][j] << " ";
fout << '\n';
}
return 0;
}