Pagini recente » Cod sursa (job #1038706) | Cod sursa (job #2331634) | Cod sursa (job #1050281) | Cod sursa (job #358405) | Cod sursa (job #1917055)
#include <fstream>
#include<vector>
#include<stack>
#include<iostream>
using namespace std;
#define DIM 100000
#define N 100100
char buff[DIM];
int poz,i,n,j,m,v[N],k,index,nr_c,l;
struct data
{
int low_link;///numarul celui mai de jos element din stiva la care se poate ajunge din nodul curent
int index;///numarul nodului in stiva
}V[N];
bool sel_st[N];
vector<int>a[N];
stack<int>S;
vector<int>curr;
vector< vector<int> >C;///lista componentelor conexe
ifstream f("ctc.in");
inline void R(int&x)
{
x=0;
while(buff[poz]<'0' || buff[poz]>'9')
if(++poz==DIM)
{
f.read(buff,DIM);
poz=0;
}
while(buff[poz]>='0' && buff[poz]<='9')
{
x=x*10+buff[poz]-'0';
if(++poz==DIM)
{
poz=0;
f.read(buff,DIM);
}
}
}
void tare_conexa(int k)
{
V[k].index=index;
V[k].low_link=index; ///la inceput fiecare nod formeaza de unul singur o componenta tare conexa
++index;
S.push(k);
sel_st[k]=1;
int nod;
for(int i=0;i<v[k];++i)
{
nod=a[k][i];
if(!V[nod].index )
{
tare_conexa(nod);
V[k].low_link=min( V[k].low_link, V[nod].low_link );
}
else
if(sel_st[nod])
V[k].low_link=min( V[k].low_link, V[nod].low_link );
}
if(V[k].index==V[k].low_link)///sunt la inceputul componentei conexe si golesc stiva
{
curr.clear();
++nr_c;
nod=S.top();S.pop();
while(k!=nod)
{
curr.push_back(nod);
sel_st[nod]=0;
nod=S.top();S.pop();
}
curr.push_back(nod);
sel_st[nod]=0;
C.push_back(curr);
}
}
int main()
{
R(n);R(m);
for(l=0;l<m;++l)
{
R(i);R(j);
a[i].push_back(j);
++v[i];
}
nr_c=0;index=1;
for(i=1;i<=n;++i)
if(!V[i].index)
tare_conexa(i);
ofstream g("ctc.out");
g<<nr_c<<'\n';
for(l=0;l<nr_c;++l)
{
//n=C[l].size;
for(i=0;i<C[l].size();++i)
g<<C[l][i]<<" ";
g<<'\n';
}
return 0;
}