Pagini recente » Cod sursa (job #2390346) | Cod sursa (job #993641) | Cod sursa (job #2359416) | Cod sursa (job #2764107) | Cod sursa (job #2940312)
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
ifstream cin("ctc.in");
ofstream cout("ctc.out");
stack<int> st;
vector<bool> inst,viz;
vector<vector<int> >sirad,ctc;
vector<int> index,low,c;
int idx,n,m;
void Dfs(int x);
void Tarjan();
int main()
{
int a,b;
cin>>n>>m;
sirad = vector<vector<int>>(n+1);
index = low = vector<int>(n+1);
inst = viz = vector<bool>(n+1);
for(int i=1;i<=m;++i)
{
cin>>a>>b;
sirad[a].push_back(b);
}
Tarjan();
return 0;
}
void Tarjan()
{
for(int i=1;i<=n;++i)
if(!viz[i])
{
Dfs(i);
}
cout<<ctc.size()<<endl;
for(auto& i : ctc)
sort(i.begin(),i.end());
sort(ctc.begin(),ctc.end());
for(auto i : ctc)
{
for(auto j : i)cout<<j<<' ';
cout<<'\n';
}
}
void Dfs(int x)
{
st.push(x);
inst[x] = true;
viz[x] = true;
index[x] = low[x] = ++idx;
for(auto i : sirad[x])
if(!viz[i])
{
Dfs(i);
low[x] = min(low[x],low[i]);
}
else if(inst[i])low[x] = min(low[x],index[i]);
if(index[x] == low[x])
{
c.clear();
while(!st.empty())
{
int a = st.top();
st.pop();
inst[a] = false;
c.push_back(a);
if(index[a] == low[a])break;
}
ctc.push_back(c);
}
}