Pagini recente » Cod sursa (job #2712836) | Cod sursa (job #102165) | Cod sursa (job #1536321) | Cod sursa (job #569276) | Cod sursa (job #500997)
Cod sursa(job #500997)
#include<stdio.h>
#include<vector>
#include <algorithm>
using namespace std;
#define nmax 1005
int n, m, nr, nrsol;
struct punct
{
int x, y;
}st[nmax*nmax];
vector<int> G[nmax], sol[nmax], vec;
int lvl[nmax], c[nmax], viz[nmax];
void citire()
{
freopen("kgb.in","r",stdin);
scanf("%d",&n);
int x, y;
while ( !feof(stdin) )
{
scanf("%d %d ", &x, &y);
G[x].push_back(y);
G[y].push_back(x);
}
}
void add(int x, int y)
{
nrsol++;
vec.push_back(x);
do{
sol[nrsol].push_back(st[nr].y);
nr--;
}while(st[nr+1].x!=x || st[nr+1].y!=y);
sol[nrsol].push_back(st[nr+1].x);
sort ( sol[nrsol].begin(), sol[nrsol].end() );
}
void dfs(int nod,int tata)
{
int i, x;
lvl[nod] = lvl[tata] + 1;
c[nod] = lvl[nod];
viz[nod] = 1;
for( i = 0; i < G[nod].size(); ++i)
{
x = G[nod][i];
if( !viz[x] )
{
st[++nr].x=nod;
st[nr].y=x;
dfs(x, nod);
if(c[x]<c[nod])
c[nod]=c[x];
if(c[x] >= lvl[nod])
add(nod,x);
}
else if(tata!=x && c[x]<c[nod])
c[nod]=c[x];
}
}
void afisare()
{
int i, j;
freopen("kgb.out","w",stdout);
if (nrsol == 1)
printf("KGB este forte");
else
{
printf("KGB nu este forte\n");
sort(vec.begin(), vec.end() );
for (i = 0; i < vec.size (); ++i) if (vec[i]!=vec[i-1]) printf("%d ", vec[i]);
printf("\n%d \n", nrsol);
for(i = 1; i <= nrsol;++i)
{
for(j = 0; j < sol[i].size(); ++j)
printf("%d ",sol[i][j]);
printf("\n");
}
}
}
int main()
{
citire ();
dfs (0,0);
afisare ();
return 0;
}