Pagini recente » Cod sursa (job #2060417) | Cod sursa (job #1195464) | Cod sursa (job #995294) | Cod sursa (job #2387867) | Cod sursa (job #2302183)
#include<fstream>
#include<stack>
#include<vector>
#include<algorithm>
#include<iterator>
using namespace std;
#define N 100001
vector<int> a[N],o,z,w,t;
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)
{
z[n]=w[n]=l;
l++,s.push(n),t[n]=1;
vector<int>::const_iterator j;
for(j=a[n].begin();j!=a[n].end();j++)
if(z[*j]==-1)
T(*j,a),w[n]=min(w[n],w[*j]);
else if(t[*j])
w[n]=min(w[n],w[*j]);
if(z[n]==w[n])
{
o.clear();
int r;
do
o.push_back(r=s.top()),s.pop(),t[r]=0;
while(r!=n);
c.push_back(o);
}
}
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);
z.resize(n),w.resize(n),t.resize(n),z.assign(n,-1),t.assign(n,0);
for(i=0;i<n;i++)
if(z[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";
}
}