제출 #2818

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
2818		ansol4328	간선 파괴 (GA5_destroy)	C++98	0 / 100	2500 ms	3012 KiB

destroy

#include<stdio.h>
#include<memory.h>
#include<stdlib.h>

int n, m, xy[702][702];
int cnt;

int bfs(int l, int e)
{
    int q[702], check[702], f, r, num;
    int i ,j;
    int c=0;

    memset(check,0,sizeof(check));
    for(i=1 ; i<=n ; i++)
    {
        if(check[i]==0)
        {
            c++;
            f=0;
            r=1;
            q[r]=i;
            check[i]=1;
            do
            {
                f++;
                num=q[f];
                for(j=1 ; j<=n ; j++)
                {
                    if((xy[num][j]!=0 && xy[num][j]<l && check[j]==0) || (xy[num][j]!=0 && xy[num][j]>e && check[j]==0))
                    {
                        r++;
                        q[r]=j;
                        check[j]=1;
                    }
                }
            }while(f<r);
        }
    }
    return c;
}

int main()
{
    int a, b, i, que;
    int max;

    scanf("%d %d",&n,&m);
    for(i=1 ; i<=m ; i++)
    {
        scanf("%d %d",&a,&b);
        xy[a][b]=i;
		xy[b][a]=i;
    }
    max=bfs(0,0);
    scanf("%d",&que);
    for(i=1 ; i<=que ; i++)
    {
        scanf("%d %d",&a,&b);
		printf("%d\n",bfs(a,b)-max+1);
    }
    return 0;
}

• Subtask 1: 0 / 25
• Subtask 2: 0 / 35
• Subtask 3: 0 / 40