Pagini recente » Cod sursa (job #1181511) | Cod sursa (job #1741460) | Cod sursa (job #2809435) | Cod sursa (job #2740758) | Cod sursa (job #1726735)
//tarjan
#include<iostream>
#include<fstream>
#include<vector>
#include<stack>
#define DX 100100
using namespace std;
fstream fin("ctc.in",ios::in),fout("ctc.out",ios::out);
int n,m,nrniv,l[DX],niv[DX],apst[DX];
typedef vector<int> TI;
typedef stack<int> SI;
vector<TI> cc;
TI v[DX],c;
SI st;
void tarjan(int nod);
void citire();
int main()
{
int i;
citire();
for(i=1;i<=n;i++)
{
if(niv[i]==0)
{
nrniv=0;
while(!st.empty()) st.pop();
tarjan(i);
}
}
fout<<cc.size()<<"\n";
for(auto x: cc)
{
for(auto y:x)
{
fout<<y<<" ";
}
fout<<"\n";
}
}
void tarjan(int nod)
{
if(niv[nod]!=0) return ;
nrniv++;
niv[nod]=l[nod]=nrniv;
int a;
apst[nod]=1;
st.push(nod);
for(auto x:v[nod])
{
if(niv[x]==0)
{
tarjan(x);
l[nod]=min(l[nod],l[x]);
}
else
{
if(apst[x]==1) //sa fie back-edge nu cross-edge(sa fie inca in stiva
{
l[nod]=min(l[nod],niv[x]);//niv in loc de l
}
}
}
if(l[nod]==niv[nod])
{
c.clear();
do
{
a=st.top();st.pop();
apst[a]=0;
c.push_back(a);
}while(!st.empty() && a!=nod);
cc.push_back(c);
}
}
void citire()
{
int a,b,i;
fin>>n>>m;
for(i=1;i<=m;i++)
{
fin>>a>>b;
v[a].push_back(b);
}
}