Pagini recente » Cod sursa (job #1658606) | Cod sursa (job #30204) | Cod sursa (job #857822) | Cod sursa (job #2153858) | Cod sursa (job #2926934)
#include <bits/stdc++.h>
using namespace std;
int n,m,i,j,nrN,nrM,op,x,y,k=0,ctc=0,inde=0;
vector<int>lowlink(100001);
vector<int> ind(100001);
stack<int> q;
vector<int>inds(100001,0);
vector<vector<int>> lista(10001);
vector<bool>verif(100001,false);
vector<int> rasp[100001];
void df(int nod)
{
q.push(nod);
verif[nod] = true;
lowlink[nod] = inde+1;
inds[nod] = inde+1;
inde = inde
+1;
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(int i=1; i<=nrN; i++)
if(!inds[i])
df(i);
}
int main()
{
ifstream f("ctc.in");
ofstream g("ctc.out");
f>>nrN>>nrM;
for(int i=1; i<=nrM; i++)
{
f>>x>>y;
lista[x].push_back(y);
}
succesor();
g<<ctc<<endl;
//cout<<ctc<<" ";
for(int i=0; i<ctc; i++)
{
for(int j=0; j<rasp[i].size(); j++)
g<<rasp[i][j]<<" ";
g<<endl;
}
return 0;
}