Cod sursa(job #1692145)

Utilizator codi22FMI Condrea Florin codi22 Data 20 aprilie 2016 11:38:50
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.64 kb
#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<<" ";
}