以上就是给各位分享洛谷P2860[USACO06JAN]冗余路径RedundantPaths(tarjan求边双联通分量)，同时本文还将给你拓展ARC062-F.PaintingGraphswithA

以上就是给各位分享洛谷 P2860 [USACO06JAN] 冗余路径 Redundant Paths (tarjan 求边双联通分量)，同时本文还将给你拓展ARC062 - F. Painting Graphs with AtCoDeer (Polya + 点双联通分量)、BZOJ1718:[USACO] Redundant Paths 分离的路径 (双连通分量)、CF 949C Data Center Maintenance_强联通分量_思维题、CF1137C Museums Tour（Tarjan，强连通分量）等相关知识，如果能碰巧解决你现在面临的问题，别忘了关注本站，现在开始吧！

• 洛谷 P2860 [USACO06JAN] 冗余路径 Redundant Paths (tarjan 求边双联通分量)
• ARC062 - F. Painting Graphs with AtCoDeer (Polya + 点双联通分量)
• BZOJ1718:[USACO] Redundant Paths 分离的路径 (双连通分量)
• CF 949C Data Center Maintenance_强联通分量_思维题
• CF1137C Museums Tour（Tarjan，强连通分量）

洛谷 P2860 [USACO06JAN] 冗余路径 Redundant Paths (tarjan 求边双联通分量)

题目描述

In order to get from one of the F (1 <= F <= 5,000) grazing fields (which are numbered 1..F) to another field, Bessie and the rest of the herd are forced to cross near the Tree of Rotten Apples. The cows are now tired of often being forced to take a particular path and want to build some new paths so that they will always have a choice of at least two separate routes between any pair of fields. They currently have at least one route between each pair of fields and want to have at least two. Of course, they can only travel on Official Paths when they move from one field to another.

Given a description of the current set of R (F-1 <= R <= 10,000) paths that each connect exactly two different fields, determine the minimum number of new paths (each of which connects exactly two fields) that must be built so that there are at least two separate routes between any pair of fields. Routes are considered separate if they use none of the same paths, even if they visit the same intermediate field along the way.

There might already be more than one paths between the same pair of fields, and you may also build a new path that connects the same fields as some other path.

为了从 F (1≤F≤5000) 个草场中的一个走到另一个，贝茜和她的同伴们有时不得不路过一些她们讨厌的可怕的树．奶牛们已经厌倦了被迫走某一条路，所以她们想建一些新路，使每一对草场之间都会至少有两条相互分离的路径，这样她们就有多一些选择．

每对草场之间已经有至少一条路径．给出所有 R (F-1≤R≤10000) 条双向路的描述，每条路连接了两个不同的草场，请计算最少的新建道路的数量，路径由若干道路首尾相连而成．两条路径相互分离，是指两条路径没有一条重合的道路．但是，两条分离的路径上可以有一些相同的草场． 对于同一对草场之间，可能已经有两条不同的道路，你也可以在它们之间再建一条道路，作为另一条不同的道路．

输入输出格式

输入格式：

Line 1: Two space-separated integers: F and R

Lines 2..R+1: Each line contains two space-separated integers which are the fields at the endpoints of some path.

输出格式：

Line 1: A single integer that is the number of new paths that must be built.

输入输出样例

7 7
1 2
2 3
3 4
2 5
4 5
5 6
5 7

2

说明

Explanation of the sample:

One visualization of the paths is:

1 2 3

+---+---+

   |   |
   |   |

6 +---+---+ 4

/ 5 / / 7 +Building new paths from 1 to 6 and from 4 to 7 satisfies the conditions.

1 2 3

+---+---+

6 +---+---+ 4

/ 5 : / :

/ :

7 + - - - - Check some of the routes:

1 – 2: 1 –> 2 and 1 –> 6 –> 5 –> 2

1 – 4: 1 –> 2 –> 3 –> 4 and 1 –> 6 –> 5 –> 4

3 – 7: 3 –> 4 –> 7 and 3 –> 2 –> 5 –> 7

Every pair of fields is, in fact, connected by two routes.

It''s possible that adding some other path will also solve the problem (like one from 6 to 7). Adding two paths, however, is the minimum.

首先，对于边双联通分量里的点我们是不用考虑的。

因此我们先用 tarjan 把边双联通分量缩出来

这样的话必定会形成一棵树

接下来考虑贪心，对于任意三个不在同一边双联通分量里且入度唯一的点

我们在他们中间连一条边，这样一定是最优的

因此我们只需要统计入度为 1 的点就行了

最后的答案为 $(ans+1)/2$

// luogu-judger-enable-o2
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stack>
#define getchar() (S == T && (T = (S = BB) + fread(BB, 1, 1 << 15, stdin), S == T) ? EOF : *S++)
char BB[1 << 15], *S = BB, *T = BB;
using namespace std;
const int MAXN=1e5+10;
inline int read()
{
    char c=getchar();int x=0,f=1;
    while(c<''0''||c>''9''){if(c==''-'')f=-1;c=getchar();}
    while(c>=''0''&&c<=''9''){x=x*10+c-''0'';c=getchar();}
    return x*f;
}
struct node
{
    int u,v,w,nxt;
}edge[MAXN];
int head[MAXN],num=1;
inline void AddEdge(int x,int y)
{
    edge[num].u=x;
    edge[num].v=y;
    edge[num].nxt=head[x];
    head[x]=num++;
}
int dfn[MAXN],low[MAXN],vis[MAXN],tot=0,colornum=0,color[MAXN],inder[MAXN];
int fuck[5001][5001];
stack<int>s;
void tarjan(int now,int fa)
{
    dfn[now]=low[now]=++tot;
    s.push(now);
    vis[now]=1;
    for(int i=head[now];i!=-1;i=edge[i].nxt)
    {
        if(!dfn[edge[i].v]&&edge[i].v!=fa) 
            tarjan(edge[i].v,now),low[now]=min(low[now],low[edge[i].v]);
        if(vis[edge[i].v]&&edge[i].v!=fa) low[now]=min(low[now],dfn[edge[i].v]);
    }
    if(dfn[now]==low[now])
    {
        int h=0;
        colornum++;
        do
        {
            h=s.top();
            color[h]=colornum;
            s.pop();
        }while(h!=now);
    }
}
int main()
{
    #ifdef WIN32
    freopen("a.in","r",stdin);
    #else
    #endif
    memset(head,-1,sizeof(head));
    int N=read(),M=read();
    for(int i=1;i<=M;i++)
    {
        int x=read(),y=read();
        AddEdge(x,y);
        AddEdge(y,x);
    }
    tarjan(1,0);
    for(int i=1;i<=num-1;i++) 
        if(color[edge[i].u]!=color[edge[i].v]&&fuck[edge[i].u][edge[i].v]==0)
            fuck[edge[i].u][edge[i].v]=1,
            inder[color[edge[i].u]]++,
            inder[color[edge[i].v]]++;
    int ans=0;
    for(int i=1;i<=colornum;i++)
        if(inder[i]==2)//双向边 
            ans++;
    printf("%d",(ans+1)>>1);    
    return 0;
}

ARC062 - F. Painting Graphs with AtCoDeer (Polya + 点双联通分量)

似乎好久都没写博客了.... 赶快来补一篇

题意

给你一个 $n$ 个点，没有重边和自环的图 .

有 $m$ 条边，每条边可以染 $1 \to k$ 中的一种颜色 .

对于任意一个简单环，可以将它的边的颜色进行旋转任意位 .

询问本质不同的染色方案数个数 .

数据范围

$1\le n \le 50, 1 \le m \le 100,1 \le k \le 100\$

题解

将边 (或者说是很多条边) 分为 $3$ 种类型 :

1. 不属于任何一个简单环，它的贡献为 $k$ .

2. 属于且仅属于一个简单环 (除了环上的边没边了) , 设环长为 $n$ . 它的贡献就是 1nn−1∑i=0kgcd(i,n)

   这个就是类似于项链染色的方案数求解，原因见 此篇博客 .

3. 属于多个环 (或者说是构成了的环，除了环上的边还有其他边) . 能够证明可以通过旋转来交换任意两条边的颜色。于是本质不同当且仅当有一种颜色数量不同，那计算的话，就是利用隔板法 把 $m$ 条边 分成 $k$ 组的方案数 (每组不一定要有边)

   那么我们肖就加入多的 $k - 1$ 个隔板，然后贡献很显然就是 (n+k−1k−1)

这个全都可以利用 $Tarjan$ 求点双联通分量 (求割点的方法) 来判断种类，并在其中计算，把所有贡献乘起来就是最后的答案了.

时间复杂度就是 $O (n+m)$ 轻松通过此题.

代码

#include <bits/stdc++.h>
#define For(i, l, r) for(int i = (l), i##end = (int)(r); i <= i##end; ++i)
#define Fordown(i, r, l) for(int i = (r), i##end = (int)(l); i >= i##end; --i)
#define Set(a, v) memset(a, v, sizeof(a))
using namespace std;

inline bool chkmin(int &a, int b) {return b < a ? a = b, 1 : 0;}
inline bool chkmax(int &a, int b) {return b > a ? a = b, 1 : 0;}

inline int read() {
    int x = 0, fh = 1; char ch = getchar();
    for (; !isdigit(ch); ch = getchar() ) if (ch == ''-'') fh = -1;
    for (; isdigit(ch); ch = getchar() ) x = (x << 1) + (x << 3) + (ch ^ ''0'');
    return x * fh;
}


void File() {
#ifdef zjp_shadow
	freopen ("F.in", "r", stdin);
	freopen ("F.out", "w", stdout);
#endif
}

const int N = 55, M = 205;

typedef long long ll;
const ll Mod = 1e9 + 7;

ll fpm(ll x, int power) {
	ll res = 1;
	for (; power; power >>= 1, (x *= x) %= Mod)
		if (power & 1) (res *= x) %= Mod;
	return res;
}

ll fac[M], ifac[M];

void Init(int maxn) {
	fac[0] = ifac[0] = 1ll;
	For (i, 1, maxn) fac[i] = fac[i - 1] * i % Mod;
	ifac[maxn] = fpm(fac[maxn], Mod - 2);
	Fordown (i, maxn - 1, 1) ifac[i] = ifac[i + 1] * (i + 1) % Mod;
}

ll C(int m, int n) {
	if (m > n || n < 0 || m < 0) return 0ll;
	return fac[n] * ifac[m] % Mod * ifac[n - m] % Mod;
}

set <int> Point;
int n, m, k; ll ans = 1ll;

ll Polya(int n) {
	ll res = 0;
	For (i, 1, n) (res += fpm(k, __gcd(n, i))) %= Mod;
	return res * fpm(n, Mod - 2) % Mod;
}

ll Permu(int m) { return C(k - 1, m + k - 1); }

vector<int> G[N];
int dfn[N], lowlink[N], sta[N], top;
void Tarjan(int u, int fa) {
	static int clk = 0;
	dfn[u] = lowlink[u] = (++ clk); sta[++ top] = u;

	for (int v : G[u]) if (!dfn[v]) {
		Tarjan(v, u), chkmin(lowlink[u], lowlink[v]);
		if (lowlink[v] >= dfn[u]) {
			Point.clear();
			int n = 0, m = 0, Last;
			do Point.insert(Last = sta[top --]), ++ n; while (Last != v);
			Point.insert(u), ++ n;
			for (int x : Point) for (int v : G[x])
				if ((bool)Point.count(v)) ++ m;
			m >>= 1;

			if (m < n) (ans *= k) %= Mod;
			if (m == n) (ans *= Polya(n)) %= Mod;
			if (m > n) (ans *= Permu(m)) %= Mod;
		}
	} else chkmin(lowlink[u], dfn[v]);
	if (!fa) -- top;
}

int main () {
	File();
	n = read(), m = read(); k = read();
	Init(m + k + 5);

	For (i, 1, m) {
		int u = read(), v = read();
		G[u].push_back(v);
		G[v].push_back(u);
	}

	For (i, 1, n) if (!dfn[i]) Tarjan(i, 0);
	printf ("%lld\n", ans);
    return 0;
}

BZOJ1718:[USACO] Redundant Paths 分离的路径 (双连通分量)

Description

Input

Output

Sample Input

Sample Output

HINT

Solution

首先可以发现，对于一个双连通分量，我们是不用处理它的
那么如果将所有边双缩成一个点的话，很显然我们可以得到一颗树
那么我们只需要处理叶子节点，在叶子节点间两两连边就好了
答案是 (叶子节点数 + 1)/2

Code

 1 #include<iostream>
 2 #include<cstring>
 3 #include<cstdio>
 4 #define N (5000+100)
 5 using namespace std;
 6 
 7 struct Edge{int to,next;} edge[N<<3];
 8 int n,m,u,v,head[N],num_edge;
 9 int Dfn[N],Low[N],dfs_num;
10 int bridge_num,ans;
11 bool Bridge[N],vis[N],dis[N][N];
12 
13 void add(int u,int v)
14 {
15     edge[++num_edge].to=v;
16     edge[num_edge].next=head[u];
17     head[u]=num_edge;
18 }
19 
20 void Tarjan(int x,int fa)
21 {
22     Dfn[x]=Low[x]=++dfs_num;
23     for (int i=head[x]; i; i=edge[i].next)
24         if (!Dfn[edge[i].to])
25         {
26             Tarjan(edge[i].to,x);
27             Low[x]=min(Low[x],Low[edge[i].to]);
28             if (Low[edge[i].to]>Dfn[x])
29                 Bridge[i]=Bridge[(i-1^1)+1]=true;
30         }
31         else if (Dfn[edge[i].to]<Dfn[x] && edge[i].to!=fa)
32             Low[x]=min(Low[x],Dfn[edge[i].to]);
33 }
34 
35 void Dfs(int x)
36 {
37     vis[x]=true;
38     for (int i=head[x]; i; i=edge[i].next)
39     {
40         if(Bridge[i]){bridge_num++; continue;}
41         if (!vis[edge[i].to]) Dfs(edge[i].to);
42     }
43 }
44 
45 int main()
46 {
47     scanf("%d%d",&n,&m);
48     for (int i=1; i<=m; ++i)
49         scanf("%d%d",&u,&v),dis[u][v]=dis[v][u]=true;
50     for (int i=1; i<=n; ++i)
51         for (int j=i+1; j<=n; ++j)
52             if (dis[i][j])
53                 add(i,j),add(j,i);
54     for (int i=1; i<=n; ++i)
55         if (!Dfn[i])
56             Tarjan(i,0);
57     for (int i=1; i<=n; ++i)
58         if (!vis[i])
59         {
60             bridge_num=0;
61             Dfs(i);
62             if (bridge_num==1)
63                 ans++;
64         }
65     printf("%d",(ans+1)/2);
66 }

CF 949C Data Center Maintenance_强联通分量_思维题

题意：
某土豪公司建立了n个数据中心，把m份资料每份在其中的两个数据中心备份。 每个数据中心在一天h个小时当中有一个小时需要维护，此时不提供资料下载服务。 现在土豪公司想要将其中若干个数据中心的维护时间向后推迟一小时，并要求一天中任意时刻每份资料都可以被下载，问最少选取多少个数据中心维护。

题解：
首先，对于两个备份的地方，我们发现只有 (C[a]+1)(C[a]+1)(C[a]+1) % h==C[b]h==C[b]h==C[b] 时，a,ba,ba,b 两个处理器需要同时后延一小时。于是，建图的条件就是只要 (C[a]+1)(C[a]+1)(C[a]+1) % h==C[b])h==C[b])h==C[b]) 就在 (a,b)(a,b)(a,b) 之间连一条边，跑一遍 tarjantarjantarjan 求出出度为 000 的大小最小的团即可。

Code:

#include<cstdio>
#include<algorithm>
#include<stack>
#include<vector>
using namespace std;
const int maxn = 1000000 + 5;
int n,m, h, C[maxn];
int head[maxn], to[maxn << 1], nex[maxn << 1], cnt, degree[maxn];
int dfn[maxn], low[maxn], scc, siz[maxn], idx, vis[maxn], answer[maxn], ans;
stack<int>S;
inline void get_min(int &a, int b){ if(a > b) a = b;}
struct Graph{
    inline void add_edge(int u,int v){
        nex[++cnt] = head[u];
        head[u] = cnt;
        to[cnt] = v;
    }
    void tarjan(int u){
        low[u] = dfn[u] = ++scc;
        S.push(u);
        vis[u] = 1;
        for(int v = head[u]; v ; v = nex[v])
        {
            if(!vis[to[v]])
            {
                tarjan(to[v]);
                low[u] = min(low[u], low[to[v]]); 
            }
            else if(!answer[to[v]]) get_min(low[u], dfn[to[v]]);
        }
        if(dfn[u] == low[u])
        {
            ++idx;
            for(;;)
            {
                int x = S.top(); S.pop();
                answer[x] = idx;
                ++siz[idx];
                if(u == x) break;
            }
        }
    }
    inline void solve(){
        siz[0] = maxn;
        for(int i = 1;i <= n; ++i) if(!vis[i]) tarjan(i);
        for(int i = 1;i <= n; ++i)
        {
            for(int j = head[i]; j ; j = nex[j])
            {
                if(answer[to[j]] != answer[i]) ++degree[answer[i]];
            }
        }
        for(int i = 1;i <= idx; ++i){
            if(degree[i]) continue;
            if(siz[ans] > siz[i]) ans = i;
        }
        printf("%d\n", siz[ans]);
        for(int i = 1;i <= n; ++i)
        {
            if(answer[i] == ans) printf("%d ",i);
        }
        printf("\n");
    }
}T;
int main()
{
    scanf("%d%d%d",&n,&m,&h);
    for(int i = 1;i <= n; ++i) scanf("%d",&C[i]);
    while(m--){
        int a,b;
        scanf("%d%d",&a,&b);
        if(((C[a] + 1) % h) == C[b]) T.add_edge(a, b);
        if(((C[b] + 1) % h) == C[a]) T.add_edge(b, a);
    }
    T.solve();
    return 0;
}

CF1137C Museums Tour（Tarjan，强连通分量）

好题，神题。

题目链接：CF 原网 洛谷

题目大意：

一个国家有 $n$ 个城市，$m$ 条有向道路组成。在这个国家一个星期有 $d$ 天，每个城市有一个博物馆。

有个旅行团在城市 $1$ 出发，当天是星期一。每天早上，如果这个城市的博物馆开了，那么可以去这个博物馆参观。每天晚上，旅行团可以选择沿一条出边前往下一个城市，或者结束旅行。一个城市可以经过多次。

请问旅行团最多能参观多少个博物馆。一个博物馆参观了多次，只计算一次。

$1\le n,m\le 10^5,1\le d\le 50$。

根据题解，先说做法：

首先拆成 $n\times d$ 个点，点 $(i,j)$ 表示当前在城市 $i$，是星期 $j$。对于原图的边 $u\rightarrow v$，连边 $(u,i)\rightarrow (v,i\bmod d+1)$。

对这个图求强连通分量，统计每个强连通分量里面有多少个不同的博物馆。

在缩点后的图中，找一条从包含 $1$ 的点开始的最长链（点权是不同博物馆个数），即为答案。

为什么呢？

首先当我们进入一个强连通分量时，肯定可以把里面所有博物馆游览完。然后也一定可以走到下一个强连通分量。

然后为什么答案不会被重复计算呢？不会出现博物馆 $u$ 在这条链里出现多次的情况吗？

我们发现，如果从 $(u,i)$ 能走到 $(u,j)$，那么从 $(u,j)$ 也能走到 $(u,i)$。

因为这代表在原图上可以走一条长 $(j-i)\bmod d$ 的链从 $u$ 走回到 $u$。现在是星期 $j$ 时，只需要走这条链 $d-1$ 次就能到星期 $i$。

那么如果从 $(u,i)$ 能走到 $(u,j)$，两点一定属于一个强连通分量。在统计强连通分量内的答案时可以判掉。于是便不可能有重复统计的情况。

那么这题就做完了…… 吗？

如果用 DFS 式的 tarjan，那么递归深度可以到 $n\times d$ 即 $5\times 10^6$，爆栈无疑。

虽然可以用 pragma 指令或者各种其他方式开栈内存，但…… 假如这是 OI 考场上呢？

那么就需要用手写栈模拟 tarjan 过程。具体写着会比较难受，我在代码里写好了注释。

当然也可能是我写复杂了，我的代码真的巨慢无比

时间复杂度 $O ((n+m)\times d)$。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=5000500;
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define ROF(i,a,b) for(int i=(a);i>=(b);i--)
#define MEM(x,v) memset(x,v,sizeof(x))
inline int read(){
    char ch=getchar();int x=0,f=0;
    while(ch<''0'' || ch>''9'') f|=ch==''-'',ch=getchar();
    while(ch>=''0'' && ch<=''9'') x=x*10+ch-''0'',ch=getchar();
    return f?-x:x;
}
inline ll getc(){
    char ch=getchar();
    while(ch<''0'' || ch>''1'') ch=getchar();
    return ch-''0'';
}
int n,m,d,head[maxn],el,to[maxn],nxt[maxn],head2[maxn],el2,to2[maxn],nxt2[maxn];
int dfn[maxn],low[maxn],dfs_clock,stk[maxn],tp,id[maxn],scc,cnt[maxn],tmp[maxn],tl,dp[maxn];
int recstk[maxn],rectp,cur[maxn];
ll vld[100010];
bool vis[maxn],ins[maxn],fst[maxn],was[maxn];
inline void add(int u,int v){
    to[++el]=v;nxt[el]=head[u];head[u]=el;
} 
inline void add2(int u,int v){
    to2[++el2]=v;nxt2[el2]=head2[u];head2[u]=el2;
}
void dfs(int s){
    recstk[rectp=1]=s;    //recstk模拟系统函数栈 
    cur[s]=head[s];    //cur[u]表示当前u的边遍历到哪一条 
    while(rectp){
        int u=recstk[rectp];
        if(fst[u]){    //fst[u]表示不是第一次入栈（那么就遍历过边） 
            if(was[u]) low[u]=min(low[u],low[to[cur[u]]]),was[u]=false;
            //was[u]表示u上一条遍历到的边是否满足!dfn[v]
            //此时就要low[u]=min(low[u],low[v])
            //不过由于模拟栈中不能方便回溯，就这么写了 
            cur[u]=nxt[cur[u]];    //向后推一条边 
        }
        else{    //u第一次进栈 
            fst[u]=true;
            dfn[u]=low[u]=++dfs_clock;
            ins[u]=true;
            stk[++tp]=u;
        }
        if(!cur[u]){    //边遍历完了 
            if(low[u]==dfn[u]){
                scc++;tl=0;    //强连通编号++ 
                do{
                    ins[stk[tp]]=false;
                    id[stk[tp]]=scc;
                    int x=(stk[tp]+d-1)/d,y=stk[tp]%d?stk[tp]%d:d;
                    //这个点是(x,y) 
                    if(!((vld[x]>>y)&1)) continue;    //(x,y)博物馆不开，不管 
                    tmp[++tl]=x;
                    if(!vis[x]) vis[x]=true,cnt[scc]++;    //如果博物馆x之前没访问过，那么新计入答案 
                }while(stk[tp--]!=u);
                FOR(i,1,tl) vis[tmp[i]]=0;    //vis清空 
            }
            rectp--;    //u退栈（相当于回溯） 
        }
        else{
            int i=cur[u],v=to[i];
            if(!dfn[v]){
                recstk[++rectp]=v;    //v进栈（相当于递归） 
                cur[v]=head[v];    //v当前遍历的边是head[v] 
                was[u]=true;    //u这条边满足!dfn[v] 
            }
            else if(ins[v]) low[u]=min(low[u],dfn[v]);
        }
    }
}
int main(){
    n=read();m=read();d=read();
    FOR(i,1,m){
        int u=read(),v=read();
        FOR(j,1,d) add((u-1)*d+j,(v-1)*d+j%d+1);
    }
    FOR(i,1,n) FOR(j,1,d) vld[i]|=getc()<<j;    //干脆压下空间……（一开始以为会MLE） 
    FOR(i,1,n*d) if(!dfn[i]) dfs(i);
    FOR(u,1,n*d) for(int i=head[u];i;i=nxt[i]){
        int v=to[i];
        if(id[u]!=id[v]) add2(id[u],id[v]);    //新图连边 
    }
    //根据tarjan的性质， 强连通编号为反向的拓扑序，所以可以从1到n直接遍历一遍 
    FOR(u,1,scc){
        for(int i=head2[u];i;i=nxt2[i]) dp[u]=max(dp[u],dp[to2[i]]);
        dp[u]+=cnt[u];
    }
    printf("%d\n",dp[id[1]]); 
}

View Code

 upd：貌似可以把 tarjan 变成 inline 就没有栈的问题了……

（代码好写 N 倍……）

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=5000500;
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define ROF(i,a,b) for(int i=(a);i>=(b);i--)
#define MEM(x,v) memset(x,v,sizeof(x))
inline int read(){
    char ch=getchar();int x=0,f=0;
    while(ch<''0'' || ch>''9'') f|=ch==''-'',ch=getchar();
    while(ch>=''0'' && ch<=''9'') x=x*10+ch-''0'',ch=getchar();
    return f?-x:x;
}
inline ll getc(){
    char ch=getchar();
    while(ch<''0'' || ch>''1'') ch=getchar();
    return ch-''0'';
}
int n,m,d,head[maxn],el,to[maxn],nxt[maxn],head2[maxn],el2,to2[maxn],nxt2[maxn];
int dfn[maxn],low[maxn],dfs_clock,stk[maxn],tp,id[maxn],scc,cnt[maxn],tmp[maxn],tl,dp[maxn];
ll vld[100010];
bool vis[maxn],ins[maxn];
inline void add(int u,int v){
    to[++el]=v;nxt[el]=head[u];head[u]=el;
} 
inline void add2(int u,int v){
    to2[++el2]=v;nxt2[el2]=head2[u];head2[u]=el2;
}
inline void dfs(int u){
    dfn[u]=low[u]=++dfs_clock;
    ins[stk[++tp]=u]=true;
    for(int i=head[u];i;i=nxt[i]){
        int v=to[i];
        if(!dfn[v]) dfs(v),low[u]=min(low[u],low[v]);
        else if(ins[v]) low[u]=min(low[u],dfn[v]);
    }
    if(dfn[u]==low[u]){
        scc++;tl=0;    //强连通编号++ 
        do{
            ins[stk[tp]]=false;
            id[stk[tp]]=scc;
            int x=(stk[tp]+d-1)/d,y=stk[tp]%d?stk[tp]%d:d;
            //这个点是(x,y) 
            if(!((vld[x]>>y)&1)) continue;    //(x,y)博物馆不开，不管 
            tmp[++tl]=x;
            if(!vis[x]) vis[x]=true,cnt[scc]++;    //如果博物馆x之前没访问过，那么新计入答案 
        }while(stk[tp--]!=u);
        FOR(i,1,tl) vis[tmp[i]]=0;    //vis清空 
    }
}
int main(){
    n=read();m=read();d=read();
    FOR(i,1,m){
        int u=read(),v=read();
        FOR(j,1,d) add((u-1)*d+j,(v-1)*d+j%d+1);
    }
    FOR(i,1,n) FOR(j,1,d) vld[i]|=getc()<<j;    //干脆压下空间……（一开始以为会MLE） 
    FOR(i,1,n*d) if(!dfn[i]) dfs(i);
    FOR(u,1,n*d) for(int i=head[u];i;i=nxt[i]){
        int v=to[i];
        if(id[u]!=id[v]) add2(id[u],id[v]);    //新图连边 
    }
    //根据tarjan的性质， 强连通编号为反向的拓扑序，所以可以从1到n直接遍历一遍 
    FOR(u,1,scc){
        for(int i=head2[u];i;i=nxt2[i]) dp[u]=max(dp[u],dp[to2[i]]);
        dp[u]+=cnt[u];
    }
    printf("%d\n",dp[id[1]]); 
}

View Code

今天的关于洛谷 P2860 [USACO06JAN] 冗余路径 Redundant Paths (tarjan 求边双联通分量)的分享已经结束，谢谢您的关注，如果想了解更多关于ARC062 - F. Painting Graphs with AtCoDeer (Polya + 点双联通分量)、BZOJ1718:[USACO] Redundant Paths 分离的路径 (双连通分量)、CF 949C Data Center Maintenance_强联通分量_思维题、CF1137C Museums Tour（Tarjan，强连通分量）的相关知识，请在本站进行查询。