Pagini recente » Cod sursa (job #834459) | Cod sursa (job #2904851) | Cod sursa (job #1890791) | Cod sursa (job #1272112) | Cod sursa (job #3137574)
#include <iostream>
#include <fstream>
#include <vector>
#include <set>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
const int Nmax=100005;
vector<int> v[Nmax],rev[Nmax],tsort;
vector<set<int>> sol;
set<int> cursol;
int viz[Nmax],viz2[Nmax];
void dfs(int nod)
{
if(viz[nod]==0)
{
viz[nod]=1;
for(int i=0;i<v[nod].size();i++)
{
if(viz[v[nod][i]]==0)
{
dfs(v[nod][i]);
}
}
tsort.push_back(nod);
}
return;
}
void ctc(int nod)
{
if(viz2[nod]==0)
{
viz2[nod]=1;
cursol.insert(nod);
for(int i=0;i<rev[nod].size();i++)
{
ctc(rev[nod][i]);
}
}
return;
}
int main()
{
int n,m,x,y;
fin>>n>>m;
for(int i=1;i<=m;i++)
{
fin>>x>>y;
v[x].push_back(y);
rev[y].push_back(x);
}
for(int i=1;i<=n;i++)
{
if(viz[i]==0)
{
dfs(i);
}
}
int cnt=0;
for(int i=tsort.size()-1;i>=0;i--)
{
if(viz2[tsort[i]]==0)
{
cnt++;
cursol.clear();
ctc(tsort[i]);
sol.push_back(cursol);
}
}
fout<<sol.size()<<'\n';
for(int i=0;i<sol.size();i++)
{
for(auto it=sol[i].begin();it!=sol[i].end();it++)
{
fout<<(*it)<<' ';
}
fout<<'\n';
}
return 0;
}