Pagini recente » Cod sursa (job #731688) | Cod sursa (job #1630771) | Cod sursa (job #1499741) | Cod sursa (job #936920) | Cod sursa (job #2047486)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
class punct
{
public:
int index=0;
int lowlink=0;
};
vector<vector<int>> ans;
int nr;
void dfs(int nod,vector<vector<int>>& path,vector<punct>& v,bitset<100010>& s,stack<int>& S)
{
v[nod].index=v[nod].lowlink=++nr;
S.push(nod);
s[nod]=1;
for(int i=0;i<path[nod].size();i++)
{
if(!v[path[nod][i]].index)
{
dfs(path[nod][i],path,v,s,S);
v[nod].lowlink=min(v[nod].lowlink,v[path[nod][i]].lowlink);
}
else if(s[path[nod][i]])
v[nod].lowlink=min(v[nod].lowlink,v[path[nod][i]].lowlink);
}
if(v[nod].index!=v[nod].lowlink)
return;
vector<int> c;
for(;;)
{
c.push_back(S.top());
s[S.top()]=0;
if(v[S.top()].index==v[S.top()].lowlink)
{
S.pop();
break;
}
S.pop();
}
ans.push_back(c);
}
int main()
{
int nodes, edges, x, y;
fin>>nodes>>edges;
vector<vector<int>> path(nodes+5);
vector<punct> v(nodes+5);
bitset<100010> s;
stack<int> S;
for(;edges;edges--)
{
fin>>x>>y;
path[x].push_back(y);
}
for(int i=1;i<=nodes;i++)
{
if(!v[i].index)
dfs(i,path,v,s,S);
}
fout<<ans.size()<<'\n';
for(int i=0;i<ans.size();i++)
{
for(int j=0;j<ans[i].size();j++)
fout<<ans[i][j]<<' ';
fout<<'\n';
}
return 0;
}