Pagini recente » Statistici UrecheToncuCotofana (ULBS_Ureche_Toncu_Cotofana) | Cod sursa (job #455506) | Cod sursa (job #1531668) | Cod sursa (job #646937) | Cod sursa (job #2367046)
#include <fstream>
#include <vector>
#include <stack>
#include <iterator>
#define maxn 100005
using namespace std;
ifstream cin("ctc.in");
ofstream cout("ctc.out");
vector <int> v[maxn],on_stack, index, low_index,viz,con;
vector < vector<int> > c;
stack <int> s;
int val=0,cnt=0,n;
void citire()
{
int m,x,y;
cin>>n>>m;
for(int i=1;i<=m;i++)
{
cin>>x>>y;
v[x].push_back(y);
}
}
void tarjan(int i)
{
int l,j;
val++;
on_stack[i]=1;
index[i]=val;
low_index[i]=val;
viz[i]=1;
l=v[i].size();
s.push(i);
for(j=0;j<l;j++)
{
if(viz[v[i][j]]==0)
{
tarjan(v[i][j]);
low_index[i]=min(low_index[i],low_index[v[i][j]]);
}
else
{
if(on_stack[v[i][j]]==1)
low_index[i]=min(low_index[i],low_index[v[i][j]]);
}
}
if(index[i]==low_index[i])
{
cnt++;
int node=s.top();
con.clear();
do
{
node=s.top();
con.push_back(node);
s.pop();
on_stack[node]=0;
}while(node!=i);
c.push_back(con);
}
}
int main()
{
int i;
citire();
viz.resize(n+1);on_stack.resize(n+1);index.resize(n+1);low_index.resize(n+1);
viz.assign(n+1,0);on_stack.assign(n+1,0);
for(i=1;i<=n;i++)
if(viz[i]==0)
{
tarjan(i);
}
cout<<cnt<<'\n';
for(int i=0;i<cnt;i++)
{
for(int j=0;j<c[i].size();j++)
cout<<c[i][j]<<" ";
cout<<'\n';
}
return 0;
}