Pagini recente » Borderou de evaluare (job #3321104) | Borderou de evaluare (job #1484691) | Borderou de evaluare (job #2348242) | Borderou de evaluare (job #1631263) | Cod sursa (job #3306501)
#include <bits/stdc++.h>
#define int long long
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
const int nmax=3e5+5;
const int mod=1e9+7;
int n,m,x,y,viz[nmax],comp[nmax],a[nmax],ap,mini;
vector <int> gr[nmax],gt[nmax];
stack <int> order;
vector <int> rez[nmax];
void dfs1(int nod)
{
viz[nod]=true;
for (int vec:gr[nod] )
if ( !viz[vec] )
dfs1(vec);
order.push(nod);
}
void dfs2(int nod, int cnx)
{
comp[nod]=cnx;
for (int vec:gt[nod] )
if ( comp[vec]==-1 )
dfs2(vec,cnx);
}
signed main()
{
f >> n >> m;
for (int i=1; i<=m; i++ )
{
int x,y;
f >> x >> y;
gr[x].push_back(y);
gt[y].push_back(x);
}
fill (viz+1,viz+n+1,false);
for (int i=1; i<=n; i++ )
if ( !viz[i] )
dfs1(i);
fill(comp+1,comp+n+1,-1);
int cnx=0;
int ways=1,cost=0;
while ( !order.empty() )
{
int u=order.top();
order.pop();
if ( comp[u]==-1 )
{
dfs2(u,cnx);
cnx++;
}
}
g << cnx << '\n';
for (int i=1; i<=n; i++ )
rez[comp[i]].push_back(i);
for (int i=0; i<cnx; i++, g << '\n' )
for (auto j:rez[i] )
g << j << " ";
return 0;
}