有向圖G=(V,E)的平方是圖G^2=(V,E^2),該圖滿足下列條件:(u,w)∈E^2當且僅當對v∈V,有(u, v)∈E,且(v,w)∈E。亦即,如果圖G中頂點u和w之間存在著一條恰包含兩條邊的路徑時,則G^2必包含該邊(u,w)。
請編程序對於給定的有向圖G,查詢邊(u,w)是否存在於平方圖G^2中。
【輸入文件】
第一行有兩個整數,v(1<=v<=100000),m(1<=m<=1000),其中v表示圖G的頂點個數,(頂點按1~v編號);
接下來有m行,每行包含4個整數u1,u2,v1,v2,表示在圖G中,頂點區間[u1,u2]中的每一個頂點至頂點區間[v1,v2]中的每一個頂點都有邊相連;
接下來有一行,一個整數n(1<=n<=1000),表示查詢的個數;
【輸出文件】
對於每一個查詢,如果結果為“是”則輸出"Yes",否則輸出"No",如果有多個查詢,每個結果單獨佔一行。
【樣例輸入】
ljb.in
6 2
1 3 5 6
4 5 2 3
1
2 3 4 6
【樣例輸出】
ljb.out
No
注:圖G與G^2中的邊數均不會超過2000000.
【我的代碼】
C++语言: Codee#25683
01 #include <cstdio>
02 #include <cstdlib>
03 #include <vector>
04 #include <algorithm>
05 #include <cstring>
06 using namespace std;
07 const int MAXN=100001;
08 typedef vector<int> Vec;
09 Vec Map[MAXN];
10
11 int N,M;
12 void init()
13 {
14 scanf("%d %d\n",&N,&M);
15 int a,b,c,d;
16 for(int i=1;i<=M;i++)
17 {
18 scanf("%d %d %d %d\n",&a,&b,&c,&d);
19 for(int j=a;j<=b;j++)
20 {
21 for(int k=c;k<=d;k++)
22 {
23 Map[j].push_back(k);
24 }
25 }
26 }
27 }
28
29 void solve()
30 {
31 int V;
32 scanf("%d\n",&V);
33 int a,b,c,d;
34 int flg[MAXN];
35 for(int i=1;i<=V;i++)
36 {
37 scanf("%d %d %d %d\n",&a,&b,&c,&d);
38 bool flag=true;
39 int num;
40 int nxt;
41 for(int j=a;j<=b;j++)
42 {
43 num=d-c+1;
44 memset(flg,0,sizeof(flg));
45 for(unsigned int k=0;num>0&&k<Map[j].size();k++)
46 {
47 nxt=Map[j][k];
48 for(unsigned int l=0;num>0&&l<Map[nxt].size();l++)
49 {
50 if(Map[nxt][l]>=c && Map[nxt][l]<=d)
51 {
52 if(!flg[Map[nxt][l]])
53 {
54 num--;
55 flg[Map[nxt][l]]=1;
56 }
57 }
58 }
59 }
60 if(num!=0)
61 {
62 flag=0;
63 break;
64 }
65 }
66 if(flag)
67 printf("Yes\n");
68 if(!flag)
69 printf("No\n");
70 }
71 }
72
73 int main()
74 {
75 freopen("ljb.in","r",stdin);
76 freopen("ljb.out","w",stdout);
77 init();
78 solve();
79 return 0;
80 }
02 #include <cstdlib>
03 #include <vector>
04 #include <algorithm>
05 #include <cstring>
06 using namespace std;
07 const int MAXN=100001;
08 typedef vector<int> Vec;
09 Vec Map[MAXN];
10
11 int N,M;
12 void init()
13 {
14 scanf("%d %d\n",&N,&M);
15 int a,b,c,d;
16 for(int i=1;i<=M;i++)
17 {
18 scanf("%d %d %d %d\n",&a,&b,&c,&d);
19 for(int j=a;j<=b;j++)
20 {
21 for(int k=c;k<=d;k++)
22 {
23 Map[j].push_back(k);
24 }
25 }
26 }
27 }
28
29 void solve()
30 {
31 int V;
32 scanf("%d\n",&V);
33 int a,b,c,d;
34 int flg[MAXN];
35 for(int i=1;i<=V;i++)
36 {
37 scanf("%d %d %d %d\n",&a,&b,&c,&d);
38 bool flag=true;
39 int num;
40 int nxt;
41 for(int j=a;j<=b;j++)
42 {
43 num=d-c+1;
44 memset(flg,0,sizeof(flg));
45 for(unsigned int k=0;num>0&&k<Map[j].size();k++)
46 {
47 nxt=Map[j][k];
48 for(unsigned int l=0;num>0&&l<Map[nxt].size();l++)
49 {
50 if(Map[nxt][l]>=c && Map[nxt][l]<=d)
51 {
52 if(!flg[Map[nxt][l]])
53 {
54 num--;
55 flg[Map[nxt][l]]=1;
56 }
57 }
58 }
59 }
60 if(num!=0)
61 {
62 flag=0;
63 break;
64 }
65 }
66 if(flag)
67 printf("Yes\n");
68 if(!flag)
69 printf("No\n");
70 }
71 }
72
73 int main()
74 {
75 freopen("ljb.in","r",stdin);
76 freopen("ljb.out","w",stdout);
77 init();
78 solve();
79 return 0;
80 }
沒有留言:
張貼留言