Untitled
unknown
plain_text
20 days ago
1.6 kB
6
Indexable
Never
#define _CRT_SECURE_NO_WARNINGS #include<iostream> using namespace std; int N,M,st,en; int f,r,mQ[10000]; int dske[101][101],index[101],visit[101]; int ans; void push(int x){ r++; mQ[r]=x; } int pop(){ f++; return mQ[f]; } void input(){ cin>>N>>M>>st>>en; for(int i=1;i<=N;i++){ index[i]=0;visit[i]=0; } int a,b; for(int i=0;i<M;i++){ cin>>a>>b; dske[a][index[a]]=b; index[a]++; } } void reset(){ for(int i=1;i<=N;i++){ visit[i]=0; } } bool BFS(){ f=r=-1; push(st); visit[st]=1; while(f!=r){ int x=pop(); for(int i=0;i<index[x];i++){ if(dske[x][i]==en) return false; if(visit[dske[x][i]]==0){ push(dske[x][i]); visit[dske[x][i]]=1; } } } return true; } int main(int argc, char** argv) { int test_case; int T; //freopen("input.txt", "r", stdin); cin >> T; for(test_case = 1; test_case <= T; ++test_case) { input(); ans=0; for(int i=1;i<=N;i++){ if(i!=st&&i!=en){ visit[i]=1; if(BFS()) ans++; reset(); } } cout << ans << endl<<endl; } return 0; } ----------------------------------------------------------------- 5 10 16 1 10 1 2 1 3 2 3 2 7 3 4 3 6 4 1 5 3 5 4 6 5 6 10 7 8 8 10 9 5 9 6 10 9 10 16 10 1 1 2 1 3 2 3 2 7 3 4 3 6 4 1 5 3 5 4 6 5 6 10 7 8 8 10 9 5 9 6 10 9 10 14 1 10 1 2 1 3 2 4 3 4 4 5 5 6 5 7 5 8 5 9 6 7 6 9 7 8 8 10 9 10 10 14 5 10 1 2 1 3 2 4 3 4 4 5 5 6 5 7 5 8 5 9 6 7 6 9 7 8 8 10 9 10 10 14 1 5 1 2 1 3 2 4 3 4 4 5 5 6 5 7 5 8 5 9 6 7 6 9 7 8 8 10 9 10
Leave a Comment