【題目描述】

Applese 有一個QQ群。在這個群中，大家互相請教問題。如 b 向 a 請教過問題，就把 a 叫做是 b 的"老板"。這樣一個群中就會有很多老板。

同時規(guī)定：如果 a 是 b 的老板，b 是 c 的老板，那么 a 也是 c 的老板。

為了不破壞群里面和諧交流的氛圍，Applese 定了一個群規(guī)：不允許出現(xiàn) a 既是 b 的老板， b 又是 a 的老板。

你需要幫助 Applese 判斷大家是否遵守了群規(guī)。

【輸入描述】

第一行兩個整數(shù) n, m，表示群里的人數(shù)以及請教問題的數(shù)量。
接下來 m 行，每行兩個整數(shù) a, b，表示 a 是 b 的"老板"，即 b 向 a 請教了一個問題。
注：無論是否違反了群規(guī)，a 都會成為 b 的老板。

1≤n≤105
1≤m≤2?105
1≤a,b≤n

【輸出描述】

對于每次提問，輸出一行"Yes"表示大家都遵守了群規(guī)，反之輸出"No"。

【樣例】

示例1

輸入
4 4
1 2
2 3
3 1
1 4
輸出
Yes
Yes
No
No

思路：

根據(jù)題意可以知道，輸出一定是若干個 Yes 后跟著若干個 No，而題目實質是要判斷有向圖是否存在環(huán)，由于題目要求在第一個出現(xiàn)環(huán)的位置開始輸出 No，由于每次都要判環(huán)一定會 TLE，無法進行在線操作，因此可以先將所有的數(shù)據(jù)讀入，通過二分來判斷最后一個?Yes 的位置來確定何時開始輸出 No

【源代碼】

#include<iostream> #include<cstdio> #include<cstdlib> #include<string> #include<cstring> #include<cmath> #include<ctime> #include<algorithm> #include<utility> #include<stack> #include<queue> #include<vector> #include<set> #include<map> #define PI acos(-1.0) #define E 1e-6 #define INF 0x3f3f3f3f #define N 100001 #define LL long long const int MOD=1e9+7; using namespace std; struct Node{int x;int num;Node(){}Node(int x,int num):x(x),num(num){} }; vector<Node> edge[N]; int vis[N]; int n,m; bool dfs(int x,int num){if(vis[x]==1)//出環(huán)return true;if(vis[x]==-1)//已訪問return false;vis[x]=1;//正在被占用for(int i=0;i<edge[x].size();i++)if(edge[x][i].num<=num&&dfs(edge[x][i].x,num))return true;vis[x]=-1;//解除占用并標記訪問return false;}bool judge(int num){memset(vis,0,sizeof(vis));for(int i=1;i<=n;i++)if(!vis[i]&&dfs(i,num))return false;return true; } int main(){cin>>n>>m;for(int i=1;i<=m;i++){int x,y;cin>>x>>y;edge[x].push_back(Node(y,i));}int pos=1;int left=1,right=m;while(left<=right){int mid=left+right>>1;if(judge(mid)){left=mid+1;pos=mid;}elseright=mid-1;}for(int i=1;i<=pos;i++)cout<<"Yes"<<endl;for(int i=pos+1;i<=m;i++)cout<<"No"<<endl;return 0; }

?

總結

以上是生活随笔為你收集整理的Applese 的 QQ 群的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。