Pagini recente » Cod sursa (job #2984328) | Cod sursa (job #903721) | Cod sursa (job #2821164) | Autentificare | Cod sursa (job #1872912)
#include <fstream>
#include <vector>
#include <bitset>
#include <map>
#define Nmax 100009
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
int n,m,x,y,nrsol;
vector <int> G[Nmax],Gt[Nmax],sol[Nmax];
bitset <Nmax> viz1,viz2,v1,v2,used;
map <int,int> ctc;
void ReadInput()
{
f>>n>>m;
for (int i=1; i<=m; ++i)
{
f>>x>>y;
G[x].push_back(y);
Gt[y].push_back(x);
}
}
void Dfs(int node, map <int,int>& v, vector<int> G[Nmax],bitset <Nmax>& viz)
{
viz[node]=1;
++v[node];
for (auto x : G[node])
if (!viz[x])
if (!used[x]) Dfs(x,v,G,viz);
}
void Solve()
{
for (int i=1; i<=n; ++i)
if (!used[i])
{
ctc.clear();
Dfs(i,ctc,G,viz1);
Dfs(i,ctc,Gt,viz2);
++nrsol;
for (auto x: ctc)
if (x.second==2)
{
used[x.first]=1;
sol[nrsol].push_back(x.first);
}
viz1.reset();
viz2.reset();
}
}
void Write()
{
g<<nrsol<<'\n';
for (int i=1; i<=nrsol; ++i)
{
for (auto x: sol[i]) g<<x<<' ';
g<<'\n';
}
}
int main()
{
ReadInput();
Solve();
Write();
f.close();
g.close();
return 0;
}