Pagini recente » Cod sursa (job #2076272) | Cod sursa (job #2226099) | Cod sursa (job #1681821) | Cod sursa (job #3130261) | Cod sursa (job #1692145)
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream f("graf.in");
ofstream g("graf.out");
long long int x,y,i,m,k,q,C[750001],n,start,fin,P[75001],P1[75001],D[75001],nr,l;
bool Op[75001];
vector <long long int> A[75001];
int main()
{
f>>n>>m>>start>>fin;
if (fin==start) {cout<<1<<start; return 0;}
if (n==2) {cout<<2<<'\n'<<start<<" "<<fin;return 0;}
for (i=1;i<=m;i++)
{
f>>x>>y;
A[x].push_back(y);
A[y].push_back(x);
}
P[start]=1;
D[start]=1;
k=0;
q=0;
C[0]=start;
while (k<=q)
{
for (i=0;i<A[C[k]].size();i++)
{
if (D[A[C[k]][i]]==0)
{
D[A[C[k]][i]]=D[C[k]]+1;
P[A[C[k]][i]]=P[C[k]];
q++;
C[q]=A[C[k]][i];
}
else if (D[A[C[k]][i]]==(D[C[k]]+1))
P[A[C[k]][i]]+=P[C[k]];
}
k++;
}
Op[fin]=true;
Op[start]=true;
C[0]=fin;
P1[fin]=1;
k=0;
q=0;
while (k<=q)
{
if (C[k]==start) break;
for (i=0;i<A[C[k]].size();i++)
{
if (D[A[C[k]][i]]+1==(D[C[k]]))
{
q++;
P1[A[C[k]][i]]+=P1[A[C[k]][i]];
Op[A[C[k]][i]]=true;
C[q]=A[C[k]][i];
}
}
k++;
}
l=0;
nr=P[fin];
P[start]=nr;
for (i=1;i<=n;i++)
if ((P[i]==nr||P1[i]==nr)&&Op[i]==true) l++;
g<<l<<'\n';
for (i=1;i<=n;i++)
if ((P[i]==nr||P1[i]==nr)&&Op[i]==true) g<<i<<" ";
}