Pagini recente » Cod sursa (job #561223) | Cod sursa (job #583641) | Cod sursa (job #2652424) | Cod sursa (job #3143420) | Cod sursa (job #2926922)
#include <bits/stdc++.h>
using namespace std;
int n,m,i,j,nrN,nrM,op,x,y,k=0,ctc=0,index=0;
vector<int>lowlink(n+1);
vector<int> ind(n+1);
stack<int> q;
vector<int>inds(n+1,0);
vector<vector<int>> lista;
vector<bool>verif(n+1,false);
vector<int> rasp[10001];
void df(int nod)
{
q.push(nod);
verif[nod] = true;
lowlink[nod] = inds[nod] = index++;
for(auto p:lista[nod])
{
if(!inds[p])
df(p);
if(verif[p])
lowlink[nod] = min(lowlink[nod],lowlink[p]);
}
if(inds[nod] == lowlink[nod]) {
rasp[ctc].push_back(nod);
int node = q.top();
q.pop();
verif[node] = false;
while(node!=nod)
{
rasp[ctc].push_back(node);
verif[node] = false;
lowlink[node] = inds[nod];
node = q.top();
q.pop();
}
ctc++;
}
}
void succesor()
{
for(i=1;i<=nrN;i++)
if(!inds[i])
df(i);
}
int main() {
ifstream f("ctc.in");
ofstream g("ctc.out");
f>>nrN>>nrM;
for(i=1;i<=m;i++)
{
f>>x>>y;
lista[x].push_back(y);
}
succesor();
g<<ctc<<endl;
//cout<<ctc<<" ";
for(i=0;i<ctc;i++)
{
for(auto qs:rasp[i])
g<<qs<< " ";
g<<endl;
}
return 0;
}