Pagini recente » Cod sursa (job #1424770) | Cod sursa (job #2302287) | Cod sursa (job #904643) | Istoria paginii runda/prep/clasament | Cod sursa (job #2302180)
#include<fstream>
#include<stack>
#include<vector>
#include<algorithm>
#include<iterator>
using namespace std;
#define N 100001
vector<int> a[N],con,idx,lowlink,in_stack;
vector<vector<int>> c;
stack<int> s;
int l,n,i,j,x,y,e,k;
void T(const int n,const vector<int> *a)
{
idx[n]=lowlink[n]=l;
l++,s.push(n),in_stack[n]=1;
vector<int>::const_iterator j;
for(j=a[n].begin();j!=a[n].end();j++)
if(idx[*j]==-1)
T(*j,a),lowlink[n]=min(lowlink[n],lowlink[*j]);
else if(in_stack[*j])
lowlink[n]=min(lowlink[n],lowlink[*j]);
if(idx[n]==lowlink[n])
{
con.clear();
int o;
do
con.push_back(o=s.top()),s.pop(),in_stack[o]=0;
while(o!=n);
c.push_back(con);
}
}
int main(void)
{
ifstream f("ctc.in");
ofstream g("ctc.out");
f>>n;
for(f>>e;e>0;e--)
f>>x>>y,a[x-1].push_back(y-1);
idx.resize(n),lowlink.resize(n),in_stack.resize(n),idx.assign(n,-1),in_stack.assign(n,0);
for(i=0;i<n;i++)
if(idx[i]==-1)
T(i,a);
k=c.size();
g<<k<<"\n";
for(i=0;i<k;i++)
{
for(j=0;j<c[i].size();j++)
g<<c[i][j]+1<<" ";
g<<"\n";
}
}