Pagini recente » Cod sursa (job #1735458) | Cod sursa (job #2629266) | Cod sursa (job #1802915) | Cod sursa (job #2460005) | Cod sursa (job #964834)
Cod sursa(job #964834)
#include<fstream>
#include<deque>
#include<set>
#include<vector>
#define pb push_back
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
int nrc,nrcc,i,n,m,x,y,viz[100100];
vector<int>l1[100100],l2[100100];
set<int>sol[100100];
deque<int>a;
inline void dfs(int x)
{
viz[x]=nrc;
for(vector<int>::iterator it=l1[x].begin();it!=l1[x].end();++it)
if(!viz[*it])
{
dfs(*it);
}
a.pb(x);
}
inline void dfs1(int x)
{
sol[nrcc].insert(x);
for(vector<int>::iterator it=l2[x].begin();it!=l2[x].end();++it)
{
if(viz[*it]==nrc)
{
viz[*it]=0;
dfs1(*it);
}
}
}
int main()
{
f>>n>>m;
for(i=1;i<=m;++i)
{
f>>x>>y;
l1[x].pb(y);
l2[y].pb(x);
}
for(i=1;i<=n;++i)
if(!viz[i])
{
++nrc;
dfs(i);
}
while(!a.empty())
{
while(!a.empty()&&!viz[a.back()])
a.pop_back();
if(a.empty())
break;
++nrcc;
nrc=viz[a.back()];
viz[a.back()]=0;
dfs1(a.back());
}
g<<nrcc<<'\n';
for(i=1;i<=nrcc;++i)
{
// g<<sol[i].size()<<' ';
for(set<int>::iterator it=sol[i].begin();it!=sol[i].end();++it)
g<<*it<<' ';
g<<'\n';
}
return 0;
}