hihocoder 1689 - 推斷大小關系（圖論+二分）

題目鏈接?https://vjudge.net/problem/HihoCoder-1689

有N個整數A₁, A₂, ... A_N，現在我們知道M條關于這N個整數的信息。每條信息是：

A_i?< A_j?或者 A_i?= A_j??

小Hi希望你能從第一條信息開始依次逐條處理這些信息。一旦能推斷出A₁和A_N的大小關系就立即停止。 ?

輸出在處理第幾條時第一次推斷出A₁和A_N的關系。如果處理完全部M條信息還是不知道A₁和A_N的大小關系，輸出-1。 ?

保證M條信息是沒有矛盾的。

Input

第一行包含兩個整數N和M。 ?

以下M行每行包含一條信息A_i?< A_j?或者 A_i?= A_j。 ?

對于30%的數據，1 ≤ N ≤ 1000, 1 ≤ M ≤ 10000 ?

對于100%的數據，1 ≤ N ≤ 100000, 1 ≤ N ≤ 1000000

Output

一個整數表示答案。

Sample Input

5 8  
A1 < A3  
A3 < A2  
A3 < A4  
A5 < A2  
A1 < A4  
A1 < A2  
A5 < A1  
A5 < A3

Sample Output

7

【思路】

? ? ? ? 圖論基礎+二分法?如果a<b就加一條有向邊a->b如果a==b就加兩條有向邊a->b和b->a，然后用一個變量index記錄這條邊是輸入中從上往下數的第幾條邊,采用二分法判斷前x條邊內否判斷出最終的大小關系，在二分的時候要用兩次dfs，一次是看能否從起點走到終點，另一次是從終點到起點，只要有一次連通著就可以，dfs搜索的時候所經過的邊不能超過mid,最后就能出答案了。輸入格式比較坑，我也是看另一個人的題解才知道的。

#include<bits/stdc++.h>
using namespace std;const int maxn = 1e5 + 50;
const int maxm = 1e6 + 50;int n, m, from, to;
int le, ri, mid;
char op[2];struct node {int to, index;node(int t, int in) :to(t), index(in) {}
};bool used[maxn];
vector<node> g[maxn];void init() {for (int i = 0; i < maxn; ++i) g[i].clear();
}bool dfs1(int u) {if (u == 1) return 1;used[u] = 1;for (int i = 0; i < g[u].size(); ++i) {node e = g[u][i];if (e.index > mid) continue;if (used[e.to]) continue;if (dfs1(e.to)) return 1;}return 0;
}bool dfs2(int u) {if (u == n) return 1;used[u] = 1;for (int i = 0; i < g[u].size(); ++i) {node e = g[u][i];if (e.index > mid) continue;if (used[e.to]) continue;if (dfs2(e.to)) return 1;}return 0;
}int main() {init();scanf("%d%d ", &n, &m);for (int i = 1; i <= m; ++i) {getchar();scanf("%d ", &from);scanf("%s ", op);getchar();scanf("%d ", &to);if (from == to) continue;if ('<' == op[0]) {g[from].push_back(node(to, i));}else if ('=' == op[0]) {g[from].push_back(node(to, i));g[to].push_back(node(from, i));}}if (n == 1) {printf("0\n");return 0;} int ans = -1;le = 0, ri = m;while (le + 1 < ri) {mid = (le + ri) >> 1;memset(used, 0, sizeof(used));bool ok = dfs1(n);memset(used, 0, sizeof(used));if (ok || dfs2(1)) { ans = mid; ri = mid; }else { le = mid; }}printf("%d\n", ans);return 0;
}