分析：因为每一组编号都是连续的嘛，所以能分成一组的尽量分，每次加边后dfs判断一下1和n是否连通.有向图的判连通没有什么很快的方法，特别注意，并查集是错的！这个算法可以得到60分.
事实上每一次都不需要从点1开始dfs，因为之前很多点都遍历到了，再从1开始会重复.如果新加的一条边的起点没有被访问过，这条边暂时是没用的，不需要再从1开始dfs,直接把这条边加进去就好了.如果这条边的起点已经被访问过了，那么从这条边的终点开始dfs就可以了，这样就节省了大量不必要的搜索，可以AC.
正解是倍增+二分.还是这样一个贪心过程.只是不能一条一条边往里面加，太慢了，可以利用倍增的思想.每次加1条边，2条边，4条边......如果加2^i条边满足要求，加2^(i+1)条边不满足要求，就在2^i和2^(i+1)之间二分，看到底加多少条边,非常奇妙.感觉就像在树上跳一样，每次可以一步一步地跳，也可以先跳一大步，如果不行就跳一小步，如果可以就再跳一小步，这种方法可以加速每次+1的枚举.
60分暴力：
#include#include #include #include using namespace std;int n, m, vis[200010], T, head[200010],ans, to[500010], nextt[500010], tot = 1;struct node{ int u, v;}e[500010];void add(int x, int y){ to[tot] = y; nextt[tot] = head[x]; head[x] = tot++;}void dfs(int u){ vis[u] = T; for (int i = head[u]; i; i = nextt[i]) { int v = to[i]; if (vis[v] != T) { vis[v] = T; dfs(v); } }}int main(){ scanf("%d%d", &n, &m); for (int i = 1; i <= m; i++) scanf("%d%d", &e[i].u, &e[i].v); for (int i = 1; i <= m; i++) { T++; add(e[i].u, e[i].v); dfs(1); if (vis[n] == T) { ans++; for (int j = 1; j <= n; j++) head[j] = 0; tot = 1; add(e[i].u, e[i].v); } } printf("%d\n", ans + 1); return 0;}
正解：
#include#include #include #include using namespace std;int n, m, vis[200010], T, head[200010], ans, to[500010], nextt[500010], tot = 1, cnt, pre[200010];struct node{ int u, v;}e[500010];void add(int x, int y){ to[tot] = y; nextt[tot] = head[x]; head[x] = tot++;}void dfs(int u){ vis[u] = T; for (int i = head[u]; i; i = nextt[i]) { int v = to[i]; if (vis[v] != T) { vis[v] = T; dfs(v); } }}int main(){ scanf("%d%d", &n, &m); for (int i = 1; i <= m; i++) scanf("%d%d", &e[i].u, &e[i].v); int i = 1; while (i <= m) { add(e[i].u, e[i].v); pre[++cnt] = e[i].u; pre[++cnt] = e[i].v; vis[1] = T; if (vis[e[i].u] == T) { dfs(e[i].v); if (vis[n] == T) { ans++; T++; for (int j = 1; j <= cnt; j++) head[pre[j]] = 0; tot = 1; cnt = 0; } else i++; } else i++; } printf("%d\n", ans); return 0;}