Pagini recente » Cod sursa (job #1041471) | Monitorul de evaluare | Cod sursa (job #1883568) | Cod sursa (job #2521373) | Cod sursa (job #836624)
Cod sursa(job #836624)
#include<stdio.h>
#include<vector>
#include<stack>
#include<bitset>
#define Nmax 100001
using namespace std;
vector<int> G[Nmax],C[Nmax];
int niv[Nmax],l[Nmax],T[Nmax];//niv[i] = nivelul nodului; l[i] cel mai de sus nod(jos ca nivel) unde poate ajunge
int N,M,nr_c;
bitset<Nmax> viz,aux;
stack< int > S;
void read_data()
{
FILE*f = fopen("biconex.in","r");
fscanf(f,"%d%d",&N,&M);
int x,y;
while(M--)
{
fscanf(f,"%d%d",&x,&y);
G[x].push_back(y);
G[y].push_back(x);
}
fclose(f);
}
int minim(int a,int b)
{
if(a<=b)
return a;
return b;
}
void get_comp(int nod)
{
aux.reset();
int x;
while(S.top() != nod)
{
x = S.top();
if(aux[x] == false)
C[nr_c].push_back(x);
aux[x] = true;
S.pop();
}
if(aux[S.top()] == false)
C[nr_c].push_back(S.top());
++nr_c;
}
void df(int nod,int nivel)
{
niv[nod] = nivel;
l[nod] = nivel;
viz[nod] = true;
S.push(nod);
int x;
for(vector<int>::iterator it = G[nod].begin();it!=G[nod].end();++it)
{
x = *it;
if(viz[x] == false)
{
S.push(nod);//adaug in stiva 1-2 2-3 3-4...
T[x] = nod;
df(x,nivel+1);
l[nod] = minim(l[x], l[nod]);//obtin minimul posibil(cu toate muchiile de intoarcere din fii)
if(l[x] >= niv[nod])//nod = T[x]
get_comp(nod);
}
else if(T[nod] != x)//inseamna ca am o muchie de intoarcere
l[nod] = minim(niv[x], l[nod]);
}
}
int main()
{
read_data();
for(int i=1;i<=N;++i)
{
if(viz[i] == false)
df(i,1);
}
FILE*g = fopen("biconex.out","w");
fprintf(g,"%d\n",nr_c);
for(int i=0;i<nr_c;++i)
{
for(vector<int>::iterator it = C[i].begin();it!=C[i].end();++it)
{
fprintf(g,"%d ",*it);
}
fprintf(g,"\n");
}
fclose(g);
return 0;
}