Pagini recente » Cod sursa (job #2041850) | Cod sursa (job #1532839) | Cod sursa (job #1491491) | Cod sursa (job #346813) | Cod sursa (job #3306799)
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream cin("ctc.in");
ofstream cout("ctc.out");
using vi = vector<int>;
int n,m,index,cnt;
vi G[100005];
vector<vi> ctc;
vi idx,low,viz,inStk,c;
/// low[x] = indexul minim la care poate ajunge din x folosind
/// o singura muchie de intoarcere
stack<int> st;
void tarjan();
void getCtc(int x)
{
while(!st.empty())
{
auto y=st.top();
st.pop();
c.push_back(y);
inStk[y]=0;
if(x==y)
break;
}
cnt++;
ctc.push_back(c);
c.clear();
}
void dfs(int x)
{
///fac subarbori
viz[x]=1;
st.push(x);
inStk[x]=1;
index++;
idx[x]=low[x]=index;
for(auto y:G[x])
{
if(!viz[y]) /// fiu
{
dfs(y);
low[x]=min(low[x],low[y]);
}
else
if(inStk[y]) /// stramos (back-edge)
low[x]=min(low[x],idx[y]);
}
if(idx[x]==low[x])
getCtc(x);
}
int main()
{
cin>>n>>m;
int x,y;
for(int i=1;i<=m;i++)
{
cin>>x>>y;
G[x].push_back(y);
}
idx=vi(n+1,0);
low=vi(n+1,0);
viz=vi(n+1,0);
inStk=vi(n+1,0);
tarjan();
cout<<cnt<<"\n";
for(auto v:ctc)
{
for(auto x:v)
cout<<x<<" ";
cout<<"\n";
}
return 0;
}
void tarjan()
{
for(int i=1;i<=n;i++)
if(!viz[i])
dfs(i);
}