Pagini recente » Cod sursa (job #3168980) | Cod sursa (job #477129) | Cod sursa (job #2875085) | Cod sursa (job #6780) | Cod sursa (job #2055350)
#include <fstream>
#include <list>
#include <queue>
#include <list>
#include <iostream>
using namespace std;
ifstream f("data.in");
ofstream g("data.out");
struct muchie
{
int x,y;
};
int main()
{
int n,m,numar_noduri=0;
f>>n>>m;
int vector_suma_vecini[n+1];
int vectori_adiacenta[n+1];
int vector_vizitat[n+1];
queue <int> q;
queue <int> solutie;
for(int i=0;i<=n+1;++i)
{
vector_suma_vecini[i]=0;
vectori_adiacenta[i]=0;
vector_vizitat[i]=0;
}
list <int> *lista_de_adiacenta= new list <int> [n+1];
for(int i=1;i<=m;++i)
{
int x,y;
f>>x>>y;
++vectori_adiacenta[x]; vector_suma_vecini[x]+=y;
++vectori_adiacenta[y]; vector_suma_vecini[y]+=x;
lista_de_adiacenta[x].push_back(y);
lista_de_adiacenta[y].push_back(x);
}
for(int i=1;i<=n;++i)
if(vectori_adiacenta[i]==1)
{
q.push(i);
vector_vizitat[i]=1;
}
while(!q.empty())
{
int x=q.front();
vector_suma_vecini[vector_suma_vecini[x]]-=x;
vectori_adiacenta[vector_suma_vecini[x]]--;
if(vector_vizitat[x]==1)
{
++numar_noduri;
solutie.push(x);
if(vector_vizitat[vector_suma_vecini[x]]==0||vector_vizitat[vector_suma_vecini[x]]==1)
vector_vizitat[vector_suma_vecini[x]]=2;
}
else
{
if(vector_vizitat[vector_suma_vecini[x]]==0)
vector_vizitat[vector_suma_vecini[x]]=1;
}
if(vectori_adiacenta[vector_suma_vecini[x]]==1)
{
q.push(vector_suma_vecini[x]);
}
q.pop();
}
g<<numar_noduri<<"\n";
while(!solutie.empty())
{
g<<solutie.front()<<" ";
solutie.pop();
}
}