This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
typedef pair <int,int> ppair;
vector <ppair> A[701];
queue <int> q;
int V, E, Q, Check[701], L, R, X;
void input(void)
{
int i, u, v;
scanf("%d %d",&V,&E);
for(i=1 ; i<=E ; i++)
{
scanf("%d %d",&u,&v);
A[u].push_back(make_pair(v,i));
A[v].push_back(make_pair(u,i));
}
scanf("%d",&Q);
}
void BFS(int start)
{
int i, j, now;
Check[start]=X;
q.push(start);
while(!q.empty())
{
now=q.front();
q.pop();
j=A[now].size();
for(i=0 ; i<j ; i++)
if(!(L<=A[now][i].second && A[now][i].second<=R) && Check[A[now][i].first]!=X)
{
Check[A[now][i].first]=X;
q.push(A[now][i].first);
}
}
}
void process(void)
{
int i, j, cnt;
for(i=1 ; i<=Q ; i++)
{
X=i;
cnt=0;
scanf("%d %d",&L,&R);
for(j=1 ; j<=V ; j++)
if(Check[j]!=X)
{
cnt++;
BFS(j);
}
printf("%d\n",cnt);
}
}
int main(void)
{
input();
process();
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |