Pagini recente » Cod sursa (job #1901321) | Cod sursa (job #2680342) | Cod sursa (job #2288611) | Cod sursa (job #1100978) | Cod sursa (job #3229808)
#include <fstream>
#include <vector>
#include <bitset>
#include <algorithm>
using namespace std;
ifstream fin ("ctc.in");
ofstream fout ("ctc.out");
vector <int> v[100001],vt[100001],sol;
vector <vector <int>> solf;
int s[100001],n,m,x,y,i,k,j;
bitset <100001> viz;
void dfs_sort_top (int nod)
{
viz[nod]=1;
for (int i=0; i<v[nod].size (); i++)
{
int vecin=v[nod][i];
if (!viz[vecin])
dfs_sort_top (vecin);
}
s[++k]=nod;
}
void dfs (int nod)
{
viz[nod]=1;
sol.push_back (nod);
for (int i=0; i<vt[nod].size (); i++)
{
int vecin=vt[nod][i];
if (!viz[vecin])
dfs (vecin);
}
}
int main ()
{
fin>>n>>m;
for (i=1; i<=m; i++)
{
fin>>x>>y;
v[x].push_back (y);
vt[y].push_back (x);
}
for (i=1; i<=n; i++)
{
if (!viz[i])
dfs_sort_top (i);
}
viz.reset ();
reverse (s+1,s+n+1);
for (i=1; i<=n; i++)
{
sol.clear ();
if (!viz[s[i]])
{
dfs (s[i]);
solf.push_back (sol);
}
}
fout<<solf.size ()<<"\n";
for (i=0; i<solf.size (); i++)
{
for (j=0; j<solf[i].size (); j++)
fout<<solf[i][j]<<" ";
fout<<"\n";
}
return 0;
}