Pagini recente » Cod sursa (job #1459277) | Cod sursa (job #1020266) | Cod sursa (job #373269) | Cod sursa (job #2378545) | Cod sursa (job #3346344)
#include <iostream>
#include <vector>
#include <stack>
#include <fstream>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
vector<vector<int>>adj;
vector<bool>V;
vector<int>nivel;
vector<int>nma;
stack<int>S;
vector<bool>inS;
vector<vector<int>>R;
int n,m,cnt=0,c;
void DFS(int k)
{
c++;
V[k]=true;
S.push(k);
nivel[k]=c;
inS[k]=true;
nma[k]=c;
for(auto x:adj[k])
if(!V[x])
{
DFS(x);
nma[k]=min(nma[k],nma[x]);
}
else if(inS[x])
nma[k]=min(nma[k],nivel[x]);
if(nivel[k]==nma[k])
{
R.push_back(vector<int>());
while(S.top()!=k)
{
inS[S.top()]=false;
R[cnt].push_back(S.top());
S.pop();
}
inS[k]=false;
R[cnt].push_back(k);
S.pop();
cnt++;
}
}
int main()
{
int x,y;
fin>>n>>m;
adj.resize(n+1);
V.resize(n+1,0);
nivel.resize(n+1);
nma.resize(n+1);
inS.resize(n+1,0);
for(int i=1; i<=m; i++)
{
fin>>x>>y;
adj[x].push_back(y);
}
for(int i=1; i<=n; i++)
if(!V[i])
DFS(i);
fout<<cnt<<endl;
for(int i=0; i<cnt; i++,fout<<endl)
for(int j:R[i])
fout<<j<<" ";
return 0;
}