精华内容
下载资源
问答
  • 有向图连通分量SCC

    2013-12-03 23:51:00
    在无向图中,如果从顶点vi到顶点vj路径,则称vi和vj连通。如果图中任意两个顶点之间都连通,则称该图为连通图,否则,称该图为非连通图,则其中的极大连通子图称为连通分量,这里所谓的极大是指子图中包含的顶点个...
    在无向图中,如果从顶点vi到顶点vj有路径,则称vi和vj连通。如果图中任意两个顶点之间都连通,则称该图为连通图,否则,称该图为非连通图,则其中的极大连通子图称为连通分量,这里所谓的极大是指子图中包含的顶点个数极大。
    直观地说,极大就是不能再大,或者说再大也不能超过自己。因此,极大连通子图就是:
      设
      1) S为G的子图,S连通,
      2) 如果有S'也是G的连通子图,且S是S'的子图,可推出S = S',
      则称S是G的极大连通子图。
      极小连通子图正好相反,极小就是不能再小,再多小一点就会不连通或点不足。因此,极小连通子图就是:
      设
      1) S为G的子图,S连通,
      2) 如果有S'也是G的连通子图,S'包含G的所有顶点,且S'是S的子图,可推出S' = S,
      则称S是G的级小连通子图。
      注:这个定义和pinejeely给出的等价。这里给出的定义比较容易验证。
    在有向图中,如果对于每一对顶点vi和vj,从vi到vj和从vj到vi都有路径,则称该图为强连通图;否则,将其中的极大强连通子图称为强连通分量。
     

    Kosaraju算法:先dfs,得到最后完成时间f,再求反图,按f递减的方向对反图再dfs一次。

      1 #include <stdio.h>
      2 #include <string.h>
      3 #include <algorithm>
      4 #include <iomanip>
      5 #include <set>
      6 #include <map>
      7 #include <vector>
      8 #include <queue>
      9 using namespace std;
     10 #define N 1000
     11 int head[N], headt[N], cnt;
     12 struct node 
     13 {
     14     int next, to;
     15 }edge[N * 2], edget[N * 2];
     16 
     17 void addedge(int from, int to)//G_T
     18 {
     19     cnt++;
     20     edge[cnt].next = head[from];
     21     edge[cnt].to = to;
     22     head[from] = cnt;
     23     //得到反图
     24     edget[cnt].next = headt[to];
     25     edget[cnt].to = from;
     26     headt[to] = cnt;
     27 }
     28 int f[N];//finishtime
     29 int d[N];//discovertime
     30 int color[N];//init 0 denote white; 1 denote gray discover; 2 denote black finish 
     31 int time; 
     32 int belong[N];//which scc
     33 int cur;//current scc
     34 void dfs_visit(int x)
     35 {
     36     color[x] = 1;
     37     d[x] = ++time;
     38     int i, j;
     39     for (i = head[x]; i; i = edge[i].next)
     40     {
     41         j = edge[i].to;
     42         if (!color[j])
     43         {
     44             dfs_visit(j);
     45         }
     46     }
     47     //color[x] = 2;
     48     f[x] = ++time;
     49 }
     50 
     51 void dfs_visit_t(int x)
     52 {
     53     color[x] = 1;
     54     //d[x] = ++time;
     55     int i, j;
     56     for (i = headt[x]; i; i = edget[i].next)
     57     {
     58         j = edget[i].to;
     59         if (!color[j])
     60         {
     61             dfs_visit_t(j);
     62         }
     63     }
     64     //color[x] = 2;
     65     //f[x] = ++time;
     66     belong[x] = cur;
     67 }
     68 
     69 bool cmp(const int &a, const int &b)
     70 {
     71     return a > b;
     72 }
     73 
     74 map<int, int, greater<int> > mp;//使用map对f[i]进行从大到小排序
     75 map<int, int>::iterator it;
     76 
     77 void init()
     78 {
     79     cnt = cur = 1;
     80     time = -1;
     81     memset(head, 0, sizeof(head));
     82     memset(f, 0, sizeof(f));
     83     memset(d, 0, sizeof(d));
     84     memset(color, 0, sizeof(color));
     85     memset(belong, 0, sizeof(belong));
     86     mp.clear();
     87 }
     88 
     89 int main()
     90 {
     91     int n, m, u, v, i;
     92     while (~scanf("%d%d", &n, &m))
     93     {
     94         init();
     95         for (i = 0; i < m; i++)
     96         {
     97             scanf("%d%d", &u, &v);
     98              addedge(u, v);
     99         } 
    100         for (i = 1; i <= n; i++)//得到f
    101             if (!color[i])
    102                 dfs_visit(i);
    103         //sort(f, f + n, cmp);
    104         for (i = 1; i <=n; i++)//对f排序
    105             mp[f[i]] = i;    
    106         memset(color, 0, sizeof(color));
    107         for (it = mp.begin(); it != mp.end(); ++it)//对反图进行dfs
    108         {
    109             if (!color[it->second])
    110             {
    111                 dfs_visit_t(it->second);
    112                 cur++;
    113             }        
    114         }    
    115         for (i = 1; i <=n; i++)
    116             printf("%d ", belong[i]);
    117     }
    118     return 0;
    119 }

    Tarjan算法只需一次dfs,而且不用求反图,dfs找最早祖先点(最先被发现)也就是寻找B边。

    使用LOW函数测试此条件
     1 #include <stdio.h>
     2 #include <string.h>
     3 #include <algorithm>
     4 #include <iomanip>
     5 #include <set>
     6 #include <map>
     7 #include <vector>
     8 #include <queue>
     9 #include <stack>
    10 #define INF 0x7fffffff
    11 using namespace std;
    12 #define N 1000
    13 
    14 stack<int> s;
    15 int head[N], cnt;
    16 struct node 
    17 {
    18     int next, to;
    19 }edge[N * 2];
    20 
    21 void addedge(int from, int to)
    22 {
    23     cnt++;
    24     edge[cnt].next = head[from];
    25     edge[cnt].to = to;
    26     head[from] = cnt;
    27 }
    28 //int f[N];//finishtime
    29 int pre[N];//discovertime 
    30 //int color[N];//init 0 denote white; 1 denote gray discover; 2 denote black finish 
    31 int time; 
    32 int id[N];//which scc
    33 int low[N];//
    34 int cur;//current scc
    35 void dfs_visit(int x)
    36 {
    37     low[x] = pre[x] = ++time;
    38     s.push(x);
    39     int i, j;
    40     for (i = head[x]; i; i = edge[i].next)
    41     {
    42         j = edge[i].to;
    43         if (!pre[j])
    44         {
    45             dfs_visit(j);
    46         }
    47         if (low[j] < low[x])//找最小的low[x],即是否存在后向边(B边)
    48             low[x] = low[j];
    49     }
    50     if (low[x] == pre[x])//找到了一个scc
    51     {
    52         do
    53         {
    54             i = s.top();
    55             s.pop();
    56             low[i] = INF;
    57             id[i] = cur;
    58         }while (i != x);
    59         cur++;
    60     }
    61 }
    62 
    63 void init()
    64 {
    65     cnt = cur = 1;
    66     time = 0;
    67     memset(head, 0, sizeof(head));
    68     memset(pre, 0, sizeof(pre));
    69     memset(low, 0, sizeof(low));
    70     memset(id, 0, sizeof(id));
    71     while (!s.empty())
    72         s.pop();
    73 }
    74 
    75 int main()
    76 {
    77     int n, m, u, v, i;
    78     while (~scanf("%d%d", &n, &m))
    79     {
    80         init();
    81         for (i = 0; i < m; i++)
    82         {
    83             scanf("%d%d", &u, &v);
    84              addedge(u, v);
    85         }     
    86         for (i = 1; i <= n; i++)
    87             if (!pre[i])
    88                 dfs_visit(i);
    89         for (i = 1; i <=n; i++)
    90             printf("%d ", id[i]);
    91     }
    92     return 0;
    93 }

    Gabow算法:思路与tarjan思路一样,但是用一个stack替代了low数组,使得交换次数减小

     1 #include <stdio.h>
     2 #include <string.h>
     3 #include <algorithm>
     4 #include <iomanip>
     5 #include <set>
     6 #include <map>
     7 #include <vector>
     8 #include <queue>
     9 #include <stack>
    10 #define INF 0x7fffffff
    11 using namespace std;
    12 #define N 1000
    13 
    14 stack<int> s;
    15 stack<int> p;
    16 int head[N], cnt;
    17 struct node 
    18 {
    19     int next, to;
    20 }edge[N * 2];
    21 
    22 void addedge(int from, int to)
    23 {
    24     cnt++;
    25     edge[cnt].next = head[from];
    26     edge[cnt].to = to;
    27     head[from] = cnt;
    28 }
    29 //int f[N];//finishtime
    30 int pre[N];//discovertime 
    31 //int color[N];//init 0 denote white; 1 denote gray discover; 2 denote black finish 
    32 int time; 
    33 int id[N];//which scc
    34 int low[N];//
    35 int cur;//current scc
    36 void dfs_visit(int x)
    37 {
    38     low[x] = pre[x] = ++time;
    39     s.push(x);
    40     p.push(x);
    41     int i, j;
    42     for (i = head[x]; i; i = edge[i].next)
    43     {
    44         j = edge[i].to;
    45         if (!pre[j])
    46             dfs_visit(j);
    47         if (!id[j])//该点未在已求的scc中
    48             while (pre[j] < pre[p.top()])存在后向边,出栈
    49                 p.pop();    
    50     }
    51     if (p.top() == x)//找到一个scc
    52     {
    53         p.pop();
    54         do
    55         {
    56             i = s.top();
    57             id[i] = cur;
    58             s.pop();
    59         }while (i != x);
    60         cur++;
    61     }
    62 }
    63 
    64 void init()
    65 {
    66     cnt = cur = 1;
    67     time = 0;
    68     memset(head, 0, sizeof(head));
    69     memset(pre, 0, sizeof(pre));
    70     memset(low, 0, sizeof(low));
    71     memset(id, 0, sizeof(id));
    72     while (!s.empty())
    73         s.pop();
    74     while (!p.empty())
    75         p.pop();
    76 }
    77 
    78 int main()
    79 {
    80     int n, m, u, v, i;
    81     while (~scanf("%d%d", &n, &m))
    82     {
    83         init();
    84         for (i = 0; i < m; i++)
    85         {
    86             scanf("%d%d", &u, &v);
    87              addedge(u, v);
    88         }     
    89         for (i = 1; i <= n; i++)
    90             if (!pre[i])
    91                 dfs_visit(i);
    92         for (i = 1; i <=n; i++)
    93             printf("%d ", id[i]);
    94     }
    95     return 0;
    96 }

     

    转载于:https://www.cnblogs.com/jecyhw/p/3456759.html

    展开全文
  • 虚拟的城市之旅 时间限制:3000 ms | 内存限制:65535 KB 难度:6 ...在A国展馆通过多维模式和高科技手段,引领参观者在展示空间踏上一段虚拟的城市之旅。...这M条道路中一部分为单向通行的道路,一部

    虚拟的城市之旅

    时间限制:3000 ms  |  内存限制:65535 KB
    难度:6
    描述

    展馆是未来城市的缩影,个人体验和互动是不变的主题。在A国展馆通过多维模式和高科技手段,引领参观者在展示空间踏上一段虚拟的城市之旅。
    梦幻国有N个城市和M条道路,每条道路连接某两个城市。任意两个城市之间最多只有一条道路直接相连。这M条道路中有一部分为单向通行的道路,一部分为双向通行的道路。
    梦幻国幅员辽阔,各地的资源分布情况各不相同,这就导致了同一种商品在不同城市的价格不一定相同。但是,同一种商品在同一个城市的买入价和卖出价始终是相同的。
    现在你已踏上一段虚拟的城市之旅。为了给你一个意外收获,允许你在旅游的同时,利用 X 商品在不同城市中的差价赚回一点旅费,但最多只能交易一次。即,在某个城市买入X 商品,可以走到另外一个城市买掉来获得旅费。当然,在赚不到差价的情况下,你也可以不进行贸易活动。
    设梦幻国N个城市的标号从1~ N,你只能从1 号城市出发,并最终在N 号城市结束自己的旅行。在旅游的过程中,任何城市可以重复经过多次,但不要求经过所有N个城市。
    例如:梦幻国有5个大城市,城市的编号和道路连接情况如下图,单向箭头表示这条道路为单向通行,双向箭头表示这条道路为双向通行。假设 X 商品在1~5 号城市的价格分别为 4,3,5,6,1。
    你可以选择如下一条线路:1235,并在2 号城市以3 的价格买入X 商品,在3号城市以5 的价格卖出X 商品,赚取的旅费数为2。
    你也可以选择如下一条线路14545,并在第1次到达5号城市时以1的价格买入X 商品,在第2次到达4号城市时以6 的价格卖出X 商品,赚取的旅费数为5。
    现在给出N个城市的X 商品价格,M条道路的信息(每条道路所连接的两个城市的编号以及该条道路的通行情况)。请问你能赚取尽可能多的旅费吗。
    输入
    有多组测试数据(以EOF为文件结束的标志)
    每组测试数据的格式如下:
    第一行:N M 分别表示城市的数目和道路的数目。
    第二行:N个正整数,每两个整数之间用一个空格隔开,分别表示1到N个城市的商品价格。
    接下来 M行,每行有3个正整数,X,Y,Z,每两个整数之间用一个空格隔开。
    如果 Z=1,表示这条道路是城市X到城市Y之间的单向道路;
    如果Z=2,表示这条道路为城市X 和城市Y之间的双向道路。

    1≤N≤100000,1≤M≤500000,
    1≤X,Y≤N,1≤Z≤2,1≤商品价格≤100。
    输出
    输出1个整数,表示最多能赚取的旅费。如果没有进行贸易,则输出0。
    样例输入
    5 5
    4 3 5 6 1
    1 2 1
    1 4 1
    2 3 2
    3 5 1
    4 5 2
    样例输出
    5


    题解:这一题并不是一个求最短路径问题。 但我们需要是SPFA算法记录在图中经过的点。 题目给出了从起点出发,到终点结束。我们跑两次最大路,第一次正向建图,从起点到终点,并记录下经过点的进价最低值。  第二次我们反向建图,从终点往开始跑最短路,这条路线上能进过的点,就代表从这些点能够跑到终点,并记录下这条线上的售价最大值。  当两种方向的路径都可以进过同一点时,那么这一点同时携带的售价与进价的差值就是在当前路径中的最大收益。


    代码如下:


    #include<cstdio>
    #include<cstring>
    #include<queue>
    #include<algorithm>
    using namespace std;
    #define maxn 100010
    int a[maxn],b[maxn],head1[maxn],head2[maxn];
    int top;
    
    struct node
    {
    	int to,next;
    }edge[maxn*5];
    
    void add(int u,int v)
    {
    	edge[top].to=v;
    	edge[top].next=head1[u];
    	head1[u]=top++;
    	
    	edge[top].to=u;
    	edge[top].next=head2[v];
    	head2[v]=top++;
    }
    
    void spfa(int s,int n)
    {
    	int i,u,v;
    	int mark1[maxn],mark2[maxn];
    	memset(mark1,0,sizeof(mark1));
    	memset(mark2,0,sizeof(mark2));
    	mark1[s]=1;
    	queue<int>q;
    	q.push(s);
    	while(!q.empty())
    	{
    		u=q.front();
    		q.pop();
    		for(i=head1[u];i!=-1;i=edge[i].next)
    		{
    			v=edge[i].to;
    			a[v]=min(a[v],a[u]);//记录下能经过点的最小进价 
    			if(!mark1[v])
    			{
    				q.push(v);
    				mark1[v]=1;
    			}
    		}
    	}
    	mark2[n]=1;
    	q.push(n);
    	while(!q.empty())//从终点走向起点,走反向边,能被走到的点代表从这些点能走到终点 
    	{
    		u=q.front();
    		q.pop();
    		for(i=head2[u];i!=-1;i=edge[i].next)
    		{
    			v=edge[i].to;
    			b[v]=max(b[v],b[u]);//记录下能经过点的最大进价 
    			if(!mark2[v])
    			{
    				q.push(v);
    				mark2[v]=2;
    			}
    		}
    	}
    	int ans=0;
    	for(i=1;i<=n;++i)//遍历每一条路径,找到所有路径上的最大值 
    	{
    		if(mark1[i]&&mark2[i])//mark1[i]为1表示从起点出发可以经过这个点,同理mark2[i]为1表示从终点出发可以经过这里 
    			ans=max(ans,b[i]-a[i]);//当两种走向都经过一个点时表示通过当前这个点一定能从起点走到终点 
    	}
    	printf("%d\n",ans);
    }
    
    int main()
    {
    	int n,m,x,y,z,i,j;
    	while(scanf("%d%d",&n,&m)!=EOF)
    	{
    		for(i=1;i<=n;++i)
    		{
    			scanf("%d",&a[i]);//a[i]存最小值 
    			b[i]=a[i];//b[i]存最大值 
    		}
    		memset(head1,-1,sizeof(head1));
    		memset(head2,-1,sizeof(head2));
    		while(m--)
    		{
    			scanf("%d%d%d",&x,&y,&z);
    			add(x,y);
    			if(z==2)
    				add(y,x);
    		}
    		spfa(1,n);
    	}
    	return 0; 
    } 



    展开全文
  • 有向图连通分量

    2020-09-23 00:03:33
    文章目录有向图连通分量1 基本概念1.1 名词解释1.2 重要性质1.3 结论2. 板子3. 例题3.1 tarjan + 缩点 + 度3.2 tarjan + 缩点 + dp3.2.1 求最长链、求方案数3.2.2 求解差分约束3.2.3 求解必经点问题 有向图连通...

    有向图强连通分量

    1 基本概念

    1.1 名词解释

    强连通分量:如果有向图中任意两点都有互相可达的路径,则此图为强连通图。有向图G的极大强连通子图称为G的强连通分量(SCC)(单点肯定都是scc,但要使scc尽可能大,所以能大尽量大)
    dfn[x]数组:时间戳,记录每一个点被dfs访问到的顺序,某个点的dfs越小,表示该点越浅,dfs数组从1开始
    low[x]:代表在dfs数中,此点以及其后代指出去的边,能返回到的最浅的点的时间戳

    Image.png

    缩点: 可以将一个强连通分量当做一个超级点,而点权按题意来定。
    示例如下:缩点前=>缩点后
    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-0lG6660V-1600790598463)(https://i.loli.net/2020/04/30/XFsdVIzpR9S4Pj7.png)]

    1.2 重要性质

    scc性质:
    (1).一个强连通分量内所有点的low[]值都相同
    (2).一个强连通分量的根的low[root]==dfn[root]
    (3).任何一个点的low[x]<=dfn[x]

    缩点性质:

    1. 遍历每一个点,遍历每一个点的出边,如果出边的两个端点分别在两个scc[1]和scc[2]内,那么建立一条新的边add(scc[1],scc[2]),表示这两个scc间有一条有向边;
    2. 同时缩点后,缩点的下标与拓扑序反序,因此把sccnum从大到小(即拓扑顺序)就可以进行动态规划求出很多东西,比如说方案,最长链等。

    1.3 结论

    和度有关性质

    1. 缩点后,对于新图而言,只需要往入度为0的点注入水流,整张图就可以都有水
    2. 缩点后,对于新图而言,把一张dag变为一张scc只需要添加max(入度为0的点数目,出度为0的点数目)条边
    3. 一张图中其他所有点都可达的点就是出度为0的点,因此,只需要缩点,新图中出度为0的超级点内含的点数目就是答案。
    4. 注意:当统计出度/入度为k(k > 0)的时候需要判断重边

    和dp有关的性质

    1. tarjan算法求出来的scc顺序是反拓扑序,因此可以利用这个性质做dp,即可用在tarjan算法的过程中做dp,也可由在tarjan算法进行完成后再做,且完成后做时间更优。
    2. 要求必须从起点开始,那么把起点当作tarjan算法的输入参数,求出来的所有缩点一定都是从起点开始的点
    3. 要求必须到达终点的情况,那么维护一个数组f2[i],f2[i]为1表示i能够到达终点,0表示不能到达终点。在tarjan求scc时,如果当前x点==n时,f[sccnum]=1
    4. 注意:当统计方案数的时候需要判重边

    2. 板子

    tarjan+缩点+拓扑序dp(反缩点顺序)

    #include<bits/stdc++.h>
    
    using namespace std;
    
    int const N = 1e5 + 10, M = 2e6 + 10;
    // dfn记录每个点的时间戳,low记录每个点的回溯值,scc[i]=x表示i在标号为x的强连通分量里,stk维护一个栈,sccnum记录强连通分量的个数
    int dfn[N], low[N], scc[N], stk[N], sccnum, top, timestamp;  
    int h1[N], e[M], ne[M], idx, h2[N];
    int n, m, x;
    int f[N], g[N];
    int scc_count[N];
    set<long long> exist;  // 本题要求方案,因此需要对新图的边去重
    
    // a->b有一条边
    void add(int a, int b, int h[]) {
        e[idx] = b, ne[idx] = h[a], h[a] = idx++;
    }
    
    // tarjan算法求强连通分量
    void tarjan(int root, int h[]) {
        if (dfn[root]) return;  // 时间戳不为0,返回
        dfn[root] = low[root] = ++timestamp;  // 记录当前点的时间戳和回溯值,初始化二者相同,而后dfn[root]>=low[root]
        stk[++top] = root;  // 把根放入栈内
        for (int i = h[root]; i != -1; i = ne[i]) { // 遍历每一个与根节点相邻的点
            int j = e[i];  // 与i相邻的点为j
            if (!dfn[j])  { // j点没有访问过
                tarjan(j, h);  // 继续dfs,得到所有以j点为根的子树内所有的low和dfn
                low[root] = min(low[root], low[j]);  // 根的low是其子树中low最小的那个
            }
            else if (!scc[j]) {// 如果j这个点还在栈内(在栈内的话不属于任何一个scc),同时一个栈内的点在一个scc内
                low[root] = min(low[root], dfn[j]);  // low代表所能到达的最小的时间戳
            }
        }
        
        // 如果root的后代不能找到更浅的节点(更小的时间戳)
        if (low[root] == dfn[root]) {  // 只有某个强连通分量的根节点的low和dfn才会相同
            sccnum++;
            while (1) {  // 出栈直到等于root
                int x = stk[top--];
                scc[x] = sccnum;
                if (x == root) break;
            }
        }
    }
    
    int main() {
        cin >> n >> m >> x;
        memset(h1, -1, sizeof h1);
        memset(h2, -1, sizeof h2);
        for (int i = 1; i <= m; ++i) {
            int a, b;
            scanf("%d %d", &a, &b);
            add(a, b, h1);
        }
    
        // tarjan求scc
        for (int i = 1; i <= n; ++i)
            if (!dfn[i]) tarjan(i, h1);
        
        // 计算每个强连通分量内点的个数
        for (int i = 1; i <= n; ++i) {
            scc_count[scc[i]] ++;
        }
        
        // 缩点
        for (int i = 1; i <= n; ++i) {
            for (int j = h1[i]; j != -1; j = ne[j]) {
                int k = e[j];
                if (scc[i] != scc[k] && !exist.count(scc[i] * 100000ll + scc[k])) {  // 本题要求方案,因此需要对新图的边去重,如果不求方案,则不需要去重
                    add(scc[i], scc[k], h2);
                    exist.insert(scc[i] * 100000ll + scc[k]);
                }
            }
        }
    
        // 按照缩点的逆序(拓扑序顺序)进行dp
        for (int i = sccnum; i; --i) {
            if (!f[i]) {  // 初始化
                f[i] = scc_count[i];
                g[i] = 1;
            }
            for (int j = h2[i]; j != -1; j = ne[j]) {
                int k = e[j];
                if (f[k] < f[i] + scc_count[k]) {
                    f[k] = f[i] + scc_count[k];
                    g[k] = g[i];
                }
                else if (f[k] == f[i] + scc_count[k]) g[k] = (g[k] + g[i]) % x;
            }
        }
    
        // 计算最大值
        int maxi = 0, sum = 0;
        for (int i = 1; i <= sccnum; ++i) {
            if (f[i] > maxi) {
                maxi = f[i];
                sum = g[i];
            }
            else if (f[i] == maxi) sum = (sum + g[i]) % x;
        }
        cout << maxi << "\n" << sum << endl;
    
        return 0;
    }
    

    3. 例题

    3.1 tarjan + 缩点 + 度

    P2341 受欢迎的牛
    题意: 每头奶牛都梦想成为牛棚里的明星。被所有奶牛喜欢的奶牛就是一头明星奶牛。所有奶牛都是自恋狂,每头奶牛总是喜欢自己的。奶牛之间的“喜欢”是可以传递的——如果 A喜欢 B,B喜欢 C,那么 A 也喜欢 C。牛栏里共有 N 头奶牛,给定一些奶牛之间的爱慕关系,请你算出有多少头奶牛可以当明星。奶牛数目N~1e4, 传递关系M~5e4
    题解: 建图,缩点,建新图,然后统计新图是否是一个连通图,如果不是,那么答案为0;如果新图是一个连通图,那么统计出度为0的点的数目,如果>=2,那么答案为0;如果为1,那么为这个超级点内的点数目。
    代码:

    #include<bits/stdc++.h>
    
    using namespace std;
    
    int const N = 1e4 + 10, M = 1e5 + 10;
    // dfn记录每个点的时间戳,low记录每个点的回溯值,scc[i]=x表示i在标号为x的强连通分量里,stk维护一个栈,sccnum记录强连通分量的个数
    int dfn[N], low[N], scc[N], stk[N], sccnum, top, timestamp;  
    int h1[N], e[M], ne[M], idx;
    int n, m, x;
    int scc_count[N], dout[N];
    
    // a->b有一条边
    void add(int a, int b, int h[]) {
        e[idx] = b, ne[idx] = h[a], h[a] = idx++;
    }
    
    // tarjan算法求强连通分量
    void tarjan(int root, int h[]) {
        if (dfn[root]) return;  // 时间戳为0,返回
        dfn[root] = low[root] = ++timestamp;  // 记录当前点的时间戳和回溯值,初始化二者相同,而后dfn[root]>=low[root]
        stk[++top] = root;  // 把根放入栈内
        for (int i = h[root]; i != -1; i = ne[i]) { // 遍历每一个与根节点相邻的点
            int j = e[i];  // 与i相邻的点为j
            if (!dfn[j]) { // j点没有访问过
                tarjan(j, h);  // 继续dfs,得到所有以j点为根的子树内所有的low和dfn
                low[root] = min(low[root], low[j]);  // 根的low是其子树中low最小的那个
            }
            else if (!scc[j]) {  // 如果j这个点还在栈内(在栈内的话不属于任何一个scc),同时一个栈内的点在一个scc内
                low[root] = min(low[root], dfn[j]);  // low代表所能到达的最小的时间戳
            }
        }
        
        // 如果root的后代不能找到更浅的节点(更小的时间戳)
        if (low[root] == dfn[root]) { // 只有某个强连通分量的根节点的low和dfn才会相同
            sccnum++;
            while (1) {  // 出栈直到等于root
                int x = stk[top--];
                scc[x] = sccnum;
                if (x == root) break;
            }
        }
    }
    
    int main() {
        cin >> n >> m;
        memset(h1, -1, sizeof h1);
        for (int i = 1; i <= m; ++i) {
            int a, b;
            scanf("%d %d", &a, &b);
            add(a, b, h1);
        }
    
        // tarjan求scc
        for (int i = 1; i <= n; ++i)
            if (!dfn[i]) tarjan(i, h1);
        
        // 计算每个强连通分量内点的个数
        for (int i = 1; i <= n; ++i) {
            scc_count[scc[i]] ++;
        }
        
        // 缩点
        for (int i = 1; i <= n; ++i) {
            for (int j = h1[i]; j != -1; j = ne[j]) {
                int k = e[j];
                if (scc[i] != scc[k]) dout[scc[i]]++;
            }
        }
    
        int cnt = 0, res = 0, cow = -1;
        for (int i = 1; i <= sccnum; ++i) if (!dout[i]) cnt++, cow = i;
    
        printf("%d", (cnt >= 2? 0: scc_count[cow]));
    
        return 0;
    }
    

    acwing367 学校网络
    题意: 给定一个有向图:N个点,求:
    1)至少要选几个顶点,才能做到从这些顶点出发,可以到达全部顶点
    2)至少要加多少条边,才能使得从任何一个顶点出发,都能到达全部顶点
    题解: 先缩点
    第一问:只需要往入度为0的点放入,即可到达其他所有的点
    第二问:max(入度为0的点的数目,出度为0的点数目)
    注意要特判下缩点后只有一个scc的情况
    代码:

    #include<bits/stdc++.h>
    
    using namespace std;
    
    int const N = 1e2 + 10, M = N * N;
    // dfn记录每个点的时间戳,low记录每个点的回溯值,scc[i]=x表示i在标号为x的强连通分量里,stk维护一个栈,sccnum记录强连通分量的个数
    int dfn[N], low[N], scc[N], stk[N], sccnum, top, timestamp;  
    int h1[N], e[M], ne[M], idx;
    int n, m, dout[N], din[N];
    
    // a->b有一条边
    void add(int a, int b, int h[]) {
        e[idx] = b, ne[idx] = h[a], h[a] = idx++;
    }
    
    // tarjan算法求强连通分量
    void tarjan(int root, int h[]) {
        if (dfn[root]) return;  // 时间戳为0,返回
        dfn[root] = low[root] = ++timestamp;  // 记录当前点的时间戳和回溯值,初始化二者相同,而后dfn[root]>=low[root]
        stk[++top] = root;  // 把根放入栈内
        for (int i = h[root]; i != -1; i = ne[i]) {
            int j = e[i];  // 与i相邻的点为j
            if (!dfn[j]) {
                tarjan(j, h);  // 继续dfs,得到所有以j点为根的子树内所有的low和dfn
                low[root] = min(low[root], low[j]);  // 根的low是其子树中low最小的那个
            }
            else if (!scc[j]) {
                low[root] = min(low[root], dfn[j]);  // low代表所能到达的最小的时间戳
            }
        }
        
        // 如果root的后代不能找到更浅的节点(更小的时间戳)
        if (low[root] == dfn[root]) {
            sccnum++;
            while (1) {
                int x = stk[top--];
                scc[x] = sccnum;
                if (x == root) break;
            }
        }
    }
    
    int main() {
        cin >> n;
        memset(h1, -1, sizeof h1);
        for (int i = 1, t; i <= n; ++i) {
            while (scanf("%d", &t) && t) add(i, t, h1);
        }
    
        // tarjan求scc
        for (int i = 1; i <= n; ++i)
            if (!dfn[i]) tarjan(i, h1);
        
        // 缩点
        for (int i = 1; i <= n; ++i) {
            for (int j = h1[i]; j != -1; j = ne[j]) {
                int k = e[j];
                if (scc[i] != scc[k]) dout[scc[i]]++, din[scc[k]]++;
            }
        }
        
        int cnt1 = 0, cnt2 = 0;
        for (int i = 1; i <= sccnum; ++i) {
            if (!dout[i]) cnt1 ++;
            if (!din[i]) cnt2 ++;
        }
        
        printf("%d\n%d\n", max(1, cnt2), (sccnum == 1? 0: max(cnt1, cnt2)));
        return 0;
    }
    

    acwing401从u到v还是从v到u?
    题意: 给定一个 n 个点 m 条边的有向图,现在要求图中任意两点u和v,均可满足u能通往v或v能通往u,请你判断要求是否能够成立。 0<n<1001,m<6000
    题解: 一张有向图的中任意两个点u和v,均可满足u能通往v或v能通往u,那么这个有向图缩点后做拓扑排序每次队列里的元素个数小于等于1
    代码:

    #include<bits/stdc++.h>
    
    using namespace std;
    
    int const N = 2e3 + 10, M = 2e4 + 10;
    // dfn记录每个点的时间戳,low记录每个点的回溯值,scc[i]=x表示i在标号为x的强连通分量里,stk维护一个栈,sccnum记录强连通分量的个数
    int dfn[N], low[N], scc[N], stk[N], sccnum, top, timestamp;  
    int h1[N], e[M], ne[M], idx, h2[N], din[N], n, m, t;
    set<long long> exist;  // 本题要求方案,因此需要对新图的边去重
    
    // a->b有一条边
    void add(int a, int b, int h[]) {
        e[idx] = b, ne[idx] = h[a], h[a] = idx++;
    }
    
    // tarjan算法求强连通分量
    void tarjan(int root, int h[]) {
        if (dfn[root]) return;  // 时间戳不为0,返回
        dfn[root] = low[root] = ++timestamp;  // 记录当前点的时间戳和回溯值,初始化二者相同,而后dfn[root]>=low[root]
        stk[++top] = root;  // 把根放入栈内
        for (int i = h[root]; i != -1; i = ne[i]) {
            int j = e[i];  // 与i相邻的点为j
            if (!dfn[j]) {
                tarjan(j, h);  // 继续dfs,得到所有以j点为根的子树内所有的low和dfn
                low[root] = min(low[root], low[j]);  // 根的low是其子树中low最小的那个
            }
            else if (!scc[j]) {
                low[root] = min(low[root], dfn[j]);  // low代表所能到达的最小的时间戳
            }
        }
        
        // 如果root的后代不能找到更浅的节点(更小的时间戳)
        if (low[root] == dfn[root]) {
            sccnum++;
            while (1)  {
                int x = stk[top--];
                scc[x] = sccnum;
                if (x == root) break;
            }
        }
    }
    
    bool top_sort() {
        queue<int> q;  // 维护一个队列
        for (int i = 1; i <= sccnum; ++i) if (!din[i]) q.push(i);  // 把入度为0的点加入队列
        // 当队列不为空时
        while (q.size()) {
            if (q.size() > 1) return 0;
            auto t = q.front();  // 取队头
            q.pop();  // 队头出队
            for (int i = h2[t]; i != -1; i = ne[i]) {
                int j = e[i];
                din[j]--;  // 队头元素出队相当于把与队头元素相连的元素的入度减一
                if (!din[j]) q.push(j);  // 把入度为0的元素放入队列
            }
        }
        return 1;
    }
    
    int main() {
        cin >> t;
        while (t--) {
            cin >> n >> m;
            memset(h1, -1, sizeof h1);
            memset(h2, -1, sizeof h2);
            memset(dfn, 0, sizeof dfn);
            memset(scc, 0, sizeof scc);
            memset(din, 0, sizeof din);
            idx = timestamp = sccnum = 0;
            exist.clear();
            for (int i = 1; i <= m; ++i) {
                int a, b;
                scanf("%d %d", &a, &b);
                add(a, b, h1);
            }
        
            // tarjan求scc
            for (int i = 1; i <= n; ++i)
                if (!dfn[i]) tarjan(i, h1);
            
            // 缩点
            for (int i = 1; i <= n; ++i) {
                for (int j = h1[i]; j != -1; j = ne[j]) {
                    int k = e[j];
                    if (scc[i] != scc[k] && !exist.count(scc[i] * 100000ll + scc[k])) {  // 本题要求方案,因此需要对新图的边去重,如果不求方案,则不需要去重
                        add(scc[i], scc[k], h2);
                        exist.insert(scc[i] * 100000ll + scc[k]);
                        din[scc[k]]++;
                    }
                }
            }
            
            if (top_sort()) cout << "Yes\n";
            else cout << "No\n";
        }
    
        return 0;
    }
    

    acwing402杀人游戏
    题意: 有N个人,其中一个杀手,其余都是平民。警察能够对每一个人进行查证,假如查证的对象是平民,他会告诉警察,他认识的所有人当中,谁是杀手,谁是平民。假如查证的对象是杀手, 杀手将会把警察干掉。每一个人都有可能是杀手,可看作他们是杀手的概率是相同的。问:根据最优的情况,保证警察自身安全并知道谁是杀手的概率最大是多少?给定M个关系,每行两个整数 x,y,表示 x 认识 y。1≤N≤105,0≤M≤3∗105
    题解: 分析可知,缩点后,每次从入度为0的点开始搜索,那么可能死亡的概率最小,且只有从链头开始搜索的时候发生一次,警察死的概率为入度为0的点数目/总点数,需要特判一种情况。
    代码:

    #include<bits/stdc++.h>
    
    using namespace std;
    
    int const N = 2e5 + 10, M = 6e5 + 10;
    // dfn记录每个点的时间戳,low记录每个点的回溯值,scc[i]=x表示i在标号为x的强连通分量里,stk维护一个栈,sccnum记录强连通分量的个数
    int dfn[N], low[N], scc[N], stk[N], sccnum, top, timestamp;  
    int h1[N], e[M], ne[M], idx, h2[N];
    int n, m;
    int scc_count[N], din[N], dout[N];
    
    // a->b有一条边
    void add(int a, int b, int h[]) {
        e[idx] = b, ne[idx] = h[a], h[a] = idx++;
    }
    
    // tarjan算法求强连通分量
    void tarjan(int root, int h[]) {
        if (dfn[root]) return;  // 时间戳不为0,返回
        dfn[root] = low[root] = ++timestamp;  // 记录当前点的时间戳和回溯值,初始化二者相同,而后dfn[root]>=low[root]
        stk[++top] = root;  // 把根放入栈内
        for (int i = h[root]; i != -1; i = ne[i]) {
            int j = e[i];  // 与i相邻的点为j
            if (!dfn[j])  {
                tarjan(j, h);  // 继续dfs,得到所有以j点为根的子树内所有的low和dfn
                low[root] = min(low[root], low[j]);  // 根的low是其子树中low最小的那个
            }
            else if (!scc[j]) {
                low[root] = min(low[root], dfn[j]);  // low代表所能到达的最小的时间戳
            }
        }
        
        // 如果root的后代不能找到更浅的节点(更小的时间戳)
        if (low[root] == dfn[root])  {
            sccnum++;
            while (1) {
                int x = stk[top--];
                scc[x] = sccnum;
                if (x == root) break;
            }
        }
    }
    
    int check(int u) {
        if (scc_count[u] != 1) return 0;
        if (!dout[u]) return 1;
        
        for (int i = h2[u]; ~i; i = ne[i]) {
            int j = e[i];
            if (din[j] == 1) return 0;
        }
        return 1;
    }
    
    int main() {
        cin >> n >> m;
        memset(h1, -1, sizeof h1);
        memset(h2, -1, sizeof h2);
        for (int i = 1; i <= m; ++i) {
            int a, b;
            scanf("%d %d", &a, &b);
            add(a, b, h1);
        }
    
        // tarjan求scc
        for (int i = 1; i <= n; ++i)
            if (!dfn[i]) tarjan(i, h1);
        
        // 计算每个强连通分量内点的个数
        for (int i = 1; i <= n; ++i) {
            scc_count[scc[i]] ++;
        }
        
        // 缩点
        for (int i = 1; i <= n; ++i) {
            for (int j = h1[i]; j != -1; j = ne[j]) {
                int k = e[j];
                if (scc[i] != scc[k]) {  // 本题要求方案,因此需要对新图的边去重,如果不求方案,则不需要去重
                    din[scc[k]] ++;
                    dout[scc[i]] ++;
                    add(scc[i], scc[k], h2);
                }
            }
        }
        
        int ans = 0, f = 0;
        for (int i = 1; i <= sccnum; ++i) {
            if (!din[i]) ans++;
        }
        
        // 特判
        for (int i = 1; i <= sccnum; ++i) {
            if (!f && !din[i] && check(i)) f = 1;
        }
        
        printf("%.6f", 1 - (double)(ans - f) / n);
    
        return 0;
    }
    

    3.2 tarjan + 缩点 + dp

    3.2.1 求最长链、求方案数

    acwing1175 最大半连通子图
    题意: 求最大半连通子图的节点数以及方案数。
    最大半连通子图:对于G的子图,如果u,v满足u->v或v->u的关系,且这个子图最大,那么就是最大半连通子图。节点数N~1e5, 边数M~1e6
    题解: 最大半连通子图就是最长链,即求最长链的长度及方案。本题缩点完求最长链的长度和方案,因此缩点完dp处理即可,f[i]表示到i点的最长链的长度,g[i]表示到i点的最长链的方案。由于缩点完之后点的下标就是按拓扑序的逆序的,因此可以按照逆序进行dp处理。处理的方法参加背包问题求方案数
    代码:

    #include<bits/stdc++.h>
    
    using namespace std;
    
    int const N = 1e5 + 10, M = 2e6 + 10;
    // dfn记录每个点的时间戳,low记录每个点的回溯值,scc[i]=x表示i在标号为x的强连通分量里,stk维护一个栈,sccnum记录强连通分量的个数
    int dfn[N], low[N], scc[N], stk[N], sccnum, top, timestamp;  
    int h1[N], e[M], ne[M], idx,h2[N];
    int n, m, x;
    int f[N], g[N];  // f[i]从s出发,i的最长链长度;g[i]从s出发,i的最长链方案;
    int scc_count[N];
    set<long long> exist;  // 本题要求方案,因此需要对新图的边去重
    
    // a->b有一条边
    void add(int a, int b, int h[]) {
        e[idx] = b, ne[idx] = h[a], h[a] = idx++;
    }
    
    // tarjan算法求强连通分量
    void tarjan(int root, int h[]) {
        if (dfn[root]) return;  // 时间戳为0,返回
        dfn[root] = low[root] = ++timestamp;  // 记录当前点的时间戳和回溯值,初始化二者相同,而后dfn[root]>=low[root]
        stk[++top] = root;  // 把根放入栈内
        for (int i = h[root]; i != -1; i = ne[i]) {
            int j = e[i];  // 与i相邻的点为j
            if (!dfn[j]) {
                tarjan(j, h);  // 继续dfs,得到所有以j点为根的子树内所有的low和dfn
                low[root] = min(low[root], low[j]);  // 根的low是其子树中low最小的那个
            }
            else if (!scc[j]) {
                low[root] = min(low[root], dfn[j]);  // low代表所能到达的最小的时间戳
            }
        }
        
        // 如果root的后代不能找到更浅的节点(更小的时间戳)
        if (low[root] == dfn[root])  {
            sccnum++;
            while (1)  {
                int x = stk[top--];
                scc[x] = sccnum;
                if (x == root) break;
            }
        }
    }
    
    int main() {
        cin >> n >> m >> x;
        memset(h1, -1, sizeof h1);
        memset(h2, -1, sizeof h2);
        for (int i = 1; i <= m; ++i) {
            int a, b;
            scanf("%d %d", &a, &b);
            add(a, b, h1);
        }
    
        // tarjan求scc
        for (int i = 1; i <= n; ++i)
            if (!dfn[i]) tarjan(i, h1);
        
        // 计算每个强连通分量内点的个数
        for (int i = 1; i <= n; ++i) {
            scc_count[scc[i]] ++;
        }
        
        // 缩点
        for (int i = 1; i <= n; ++i) {
            for (int j = h1[i]; j != -1; j = ne[j]) {
                int k = e[j];
                if (scc[i] != scc[k] && !exist.count(scc[i] * 100000ll + scc[k])) { // 本题要求方案,因此需要对新图的边去重,如果不求方案,则不需要去重
                    add(scc[i], scc[k], h2);
                    exist.insert(scc[i] * 100000ll + scc[k]);
                }
            }
        }
    
        // 按照缩点的逆序(拓扑序顺序)进行dp
        for (int i = sccnum; i; --i) {
            if (!f[i]) {
                f[i] = scc_count[i];
                g[i] = 1;
            }
            for (int j = h2[i]; j != -1; j = ne[j]) {
                int k = e[j];
                if (f[k] < f[i] + scc_count[k]) {
                    f[k] = f[i] + scc_count[k];
                    g[k] = g[i];
                }
                else if (f[k] == f[i] + scc_count[k]) g[k] = (g[k] + g[i]) % x;
            }
        }
    
        // 计算最大值
        int maxi = 0, sum = 0;
        for (int i = 1; i <= sccnum; ++i) {
            if (f[i] > maxi) {
                maxi = f[i];
                sum = g[i];
            }
            else if (f[i] == maxi) sum = (sum + g[i]) % x;
        }
        cout << maxi << "\n" << sum << endl;
    
        return 0;
    }
    

    3.2.2 求解差分约束

    acwing1169糖果
    题意:
    幼儿园里有 N 个小朋友,老师现在想要给这些小朋友们分配糖果,要求每个小朋友都要分到糖果。老师需要满足小朋友们的 K 个要求。老师想知道他至少需要准备多少个糖果。
    要求有5种:
    如果 X=1.表示第 A 个小朋友分到的糖果必须和第 B 个小朋友分到的糖果一样多。
    如果 X=2,表示第 A 个小朋友分到的糖果必须少于第 B 个小朋友分到的糖果。
    如果 X=3,表示第 A 个小朋友分到的糖果必须不少于第 B 个小朋友分到的糖果。
    如果 X=4,表示第 A 个小朋友分到的糖果必须多于第 B 个小朋友分到的糖果。
    如果 X=5,表示第 A 个小朋友分到的糖果必须不多于第 B 个小朋友分到的糖果。
    N~1e5, K~1e5, 1 <=A, B <= N
    题解: 原来的思路是建图后,做差分约束,跑spfa,一旦发现出现正环那么无解,否则求出最长距离,然后累加,这种方法时间卡在spfa上,
    spfa有可能跑出O(nm)的时间导致超时
    由于数据比较特殊,只有0和1两种,那么可以换一个方法:
    对于每一个环,它一定是属于scc,而只要出现1条边权为1的边那么就是出现正环,所有我们可以缩点后,判断每个scc内部是否出现
    边权为1的边,一旦出现就是正环,无解;如果没有出现,那么有解,求完scc后缩点,然后按照缩点的逆序(拓扑序)进行dp,求出
    最长链dis,然后答案就是每个超级点内点的个数*这个点的最长距离的累加值。
    代码:

    #include<bits/stdc++.h>
    
    using namespace std;
    
    typedef long long LL;
    
    int const N = 1e5 + 10, M = 6e5 + 10;
    // dfn记录每个点的时间戳,low记录每个点的回溯值,scc[i]=x表示i在标号为x的强连通分量里,stk维护一个栈,sccnum记录强连通分量的个数
    int dfn[N], low[N], scc[N], stk[N], sccnum, top, timestamp;  
    int h1[N], h2[N], e[M], ne[M], idx, w[M];
    int n, m;
    int scc_count[N];
    int dis[N];
    
    // a->b有一条边
    void add(int a, int b, int c, int h[]) {
        e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
    }
    
    // tarjan算法求强连通分量
    void tarjan(int root, int h[]) {
        if (dfn[root]) return;  // 时间戳不为0,返回
        dfn[root] = low[root] = ++timestamp;  // 记录当前点的时间戳和回溯值,初始化二者相同,而后dfn[root]>=low[root]
        stk[++top] = root;  // 把根放入栈内
        for (int i = h[root]; i != -1; i = ne[i])  {
            int j = e[i];  // 与i相邻的点为j
            if (!dfn[j]) {
                tarjan(j, h);  // 继续dfs,得到所有以j点为根的子树内所有的low和dfn
                low[root] = min(low[root], low[j]);  // 根的low是其子树中low最小的那个
            }
            else if (!scc[j])  {
                low[root] = min(low[root], dfn[j]);  // low代表所能到达的最小的时间戳
            }
        }
        
        // 如果root的后代不能找到更浅的节点(更小的时间戳)
        if (low[root] == dfn[root]) {
            sccnum++;
            while (1) {
                int x = stk[top--];
                scc[x] = sccnum;
                if (x == root) break;
            }
        }
    }
    
    int main() {
        cin >> n >> m;
        memset(h1, -1, sizeof h1);
        memset(h2, -1, sizeof h2);
    
        // 建图
        for (int i = 0, x, a, b; i < m; ++i) {
            scanf("%d %d %d", &x, &a, &b);
            if (x == 1) add(a, b, 0, h1), add(b, a, 0, h1);
            else if (x == 2) add(a, b, 1, h1);
            else if (x == 3) add(b, a, 0, h1);
            else if (x == 4) add(b, a, 1, h1);
            else if (x == 5) add(a, b, 0, h1);
        }
    
        // tarjan求scc
        for (int i = 1; i <= n; ++i)
            if (!dfn[i]) tarjan(i, h1);
        
        // 计算每个强连通分量内点的个数
        for (int i = 1; i <= n; ++i) scc_count[scc[i]] ++;
        
        // 缩点建图(顺便判断是否有解)
        bool success = true;
        for (int i = 1; i <= n; i ++ ) {
            for (int j = h1[i]; ~j; j = ne[j]) {
                int k = e[j];
                int a = scc[i], b = scc[k];
                if (a == b) {
                    if (w[j] > 0) {
                        success = false;
                        break;
                    }
                }
                else add(a, b, w[j], h2);
            }
            if (!success) break;
        }
    
        // 做dp求最长路
        if (!success) puts("-1");
        else {
            for (int i = sccnum; i; i--) dis[i] = 1;
            for (int i = sccnum; i; i -- ) {
                for (int j = h2[i]; ~j; j = ne[j]) {
                    int k = e[j];
                    dis[k] = max(dis[k], dis[i] + w[j]);
                }
            }
    
        // 求答案
        LL res = 0;
        for (int i = 1; i <= sccnum; i ++ ) res += (LL)dis[i] * scc_count[i];
        printf("%lld\n", res);
        }
        return 0;
    }
    

    3.2.3 求解必经点问题

    acwing341最优贸易
    题意: 给出 n个城市的水晶球价格,m 条道路的信息。在1->N路径(可以不简单)上买1次卖1次,最多能赚多少钱。
    题解: 本题要找1 ~ n上最大的点和最小的点
    考虑dp求解,维护数组f1[i]表示i点开始到n点的最大价值,然后去枚举i为买的点,答案即为max{val[i]-f1[i]}
    但是本题可能存在环,因此考虑tarjan算法缩点变成dag
    本题的难点在于要求当前的点i必须是从1开始,到n结束
    从1开始好处理,tarjan算法的时候只做1为起点的tarjan,这样求出来的都是从1开始的
    而到n结束就必须维护一个数组f2[i]表示i是否能够到n点,f2[i]为1表示i能够到n点,为0表示不能到n点,每次都必须更新f2
    维护数组f1[i]表示i点开始到n点的最大价值,当且仅当f2[i]=1才能转移,f1[i]=max[max{f1[u]}, val[i]]
    代码:

    #include<bits/stdc++.h>
    
    using namespace std;
    
    typedef pair<int, int> PII;
    
    int const N = 2e5 + 10, M = 2e6 + 10;
    // dfn记录每个点的时间戳,low记录每个点的回溯值,scc[i]=x表示i在标号为x的强连通分量里,stk维护一个栈,sccnum记录强连通分量的个数
    int dfn[N], low[N], scc[N], stk[N], sccnum, top, timestamp;  
    int h1[N], e[M], ne[M], idx, h2[N], w[N];
    int n, m;
    int f1[N], f2[N]; //f1[i]表示i点开始到n点的最大价值, f2[i]为1表示i能够到n点,为0表示不能到n点
    PII scc_count[N];  // first为max,second为min
    
    // a->b有一条边
    void add(int a, int b, int h[]) {
        e[idx] = b, ne[idx] = h[a], h[a] = idx++;
    }   
    
    // tarjan算法求强连通分量
    void tarjan(int root, int h[]) {
        if (dfn[root]) return;  // 时间戳为0,返回
        dfn[root] = low[root] = ++timestamp;  // 记录当前点的时间戳和回溯值,初始化二者相同,而后dfn[root]>=low[root]
        stk[++top] = root;  // 把根放入栈内
        for (int i = h[root]; i != -1; i = ne[i]) {
            int j = e[i];  // 与i相邻的点为j
            if (!dfn[j])  {
                tarjan(j, h);  // 继续dfs,得到所有以j点为根的子树内所有的low和dfn
                low[root] = min(low[root], low[j]);  // 根的low是其子树中low最小的那个
            }
            else if (!scc[j])  {
                low[root] = min(low[root], dfn[j]);  // low代表所能到达的最小的时间戳
            }
        }
        
        // 如果root的后代不能找到更浅的节点(更小的时间戳)
        if (low[root] == dfn[root]) {
            sccnum++;
            scc_count[sccnum].first = -1;  // 计算最大值和最小值
            scc_count[sccnum].second = 1e9;
            while (1) {
                int x = stk[top--];
                if (x == n) f2[sccnum] = 1;
                scc[x] = sccnum;
                scc_count[sccnum].first = max(scc_count[sccnum].first, w[x]);
                scc_count[sccnum].second = min(scc_count[sccnum].second, w[x]);
                if (x == root) break;
            }
        }
    }
    
    int main() {
        cin >> n >> m;
        memset(h1, -1, sizeof h1);
        memset(h2, -1, sizeof h2);
        memset(f1, -1, sizeof f1);
        
        for (int i = 1; i <= n; ++i) scanf("%d", &w[i]);
        for (int i = 1, a, b, t; i <= m; ++i) {
            scanf("%d %d %d", &a, &b, &t);
            add(a, b, h1);
            if (t == 2) add(b, a, h1);
        }
    
        // tarjan求scc
        tarjan(1, h1);  // 这样保证后面缩点的所有点都是从1开始
        
        // 缩点
        for (int i = 1; i <= n; ++i)
            for (int j = h1[i]; j != -1; j = ne[j]) {
                int k = e[j];
                if (scc[i] != scc[k] && scc[i] && scc[k]) add(scc[i], scc[k], h2);
            }
        
        // 反拓扑序做dp
        int ans = 0;
        for (int i = 1; i <= sccnum; ++i) {  
            int maxv = -1;
            for (int j = h2[i]; ~j; j = ne[j]) {
                int k = e[j];
                f2[i] |= f2[k];  // 更新i是否能够到达终点的情况
                if (f2[k]) maxv = max(maxv, f1[k]);  // 更新能够到达终点的最大值
            }
            if (f2[i]) {  // 只要f2为1才更新
                f1[i] = max(scc_count[i].first, maxv);
                ans = max(ans, f1[i] - scc_count[i].second);
            }
        }
    
        cout << ans;
    
        return 0;
    }
    
    展开全文
  • Tarjan有向图连通分量 本文仅供娱乐,不喜勿喷 一、强连通分量 有向图连通分量:在有向图G中,如果两个顶点vi,vj间(vi>vj)有一条从vi到vj的有向路径,同时还有一条从vj到vi的有向路径,则称两个顶点强连通...

    Tarjan有向图强连通分量

    本文仅供娱乐,不喜勿喷

    一、强连通分量

    有向图强连通分量:在有向图G中,如果两个顶点vi,vj间(vi>vj)有一条从vi到vj的有向路径,同时还有一条从vj到vi的有向路径,则称两个顶点强连通(strongly connected)。如果有向图G的每两个顶点都强连通,称G是一个强连通图。有向图的极大强连通子图,称为强连通分量(strongly connected components)。

    通俗地说:一个强连通分量内的点两两相互可达。

    它可能长得像这样

    avatar

    丑陋的图

    二、咋求啊?

    Tarjan——一种由Robert Tarjan提出的求解有向图强连通分量的线性时间的算法

    我们考虑DFS的时候记录一些东西
    ​ 1. dfn[u] 第一次访问u的时间戳
    ​ 2. low[u] u及u的子孙中所能到达的最小的时间戳 (啥啊?请看下文)

    我这里刚好有一些记录这2个东西的方法:
    ​ 1. 如果从u出发的点已经没了, 则low[u]=dfn[u]=当前时间戳
    ​ 2. 如果下一个将访问的点v未被访问过(即dfn[v]=0), 则v在u的子孙中low[u]应该和low[v]取最小值
    ​ 3.如果下一个将访问的点v已经被访问过了,那么只有返祖边有用对吧?只需用返祖边连接的另一节点的dfn来更新当前的low
    ​ (假设通过横插边与刚访问的东西连接了,那么是不是不可能与刚访问的组成强连通分量吧?,如果可以的话,刚刚就应该做到这个u了,对吧)

    咱们再看一张不优美的图

    avatar

    ​ 1. 图中黑点即为原图中的点
    ​ 2. 黑边是我们在dfs时经过的边,我们叫它树边
    ​ 3. 红边为其他比较奇怪的边, 标号为1、2的边我们叫它横叉边,标号为3的边我们叫他反祖边

    让我们稍微想想:如果u的子孙中可以到达时间戳比u更小的, 是不是他们是强连通的。但是我们要求的是强连通分量呀。

    那么再继续想想——是不是如果u的子孙中可以到达时间戳中的最小值和dfn[u]一样,那么是不是u就是这个强连通分量的根啊(好像是叫根的)。

    但是如果满足这个条件,并不是u的所有子孙和他都可以组成一个强连通分量。
    如图所示:

    avatar

    咋整呢?一个栈就可以了。每次访问u就加到栈里,如果u为一个强连通分量的根,那么就把栈顶至u的元素都弹出,他们都是一个强连通分量的,这个得自己想想。

    好像挺简单的,看看代码吧。

    #include <stdio.h>
    #include <cstdlib>
    #include <cstring>
    #include <cmath>
    #include <vector>
    #include <iostream>
    #include <algorithm>
    using namespace std;
    const int MAXN = 10005;
    const int MAXM = 100005;
    struct Edge {
        int to, nxt;
    } edge[MAXM];
    vector <int> scc[MAXN];
    int fir[MAXN], ecnt, stk[MAXN], dfn[MAXN], low[MAXN];
    int n, m, scnt, timer, top, col[MAXN];
    void addedge(int u, int v) {
        edge[++ecnt].to = v;
        edge[ecnt].nxt = fir[u];
        fir[u] = ecnt;
    }
    void tarjan(int u) {
        dfn[u] = low[u] = ++timer;
        stk[++top] = u;
        for (int e = fir[u]; e; e = edge[e].nxt) {
            int v = edge[e].to;
            if (!dfn[v]) {                          //未访问过,即v位u的子孙
                tarjan(v);
                low[u] = min(low[u], low[v]);         //用他的low更新
            } else if (!col[v])                     //没有颜色标记,即还未确定所在强连通分量,即为祖先
                low[u] = min(low[u], dfn[v]);        //用dfn更新
        }
        if (dfn[u] == low[u]) {
            col[u] = ++scnt;
            scc[scnt].push_back(u);
            while (stk[top] != u) {                 //弹出top至u的节点
                scc[scnt].push_back(stk[top]);
                col[stk[top--]] = scnt;
            }
            --top;
        }
    }
    int main() {
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= n; ++i)
            scanf("%d", &val[i]);
        for (int i = 1; i <= m; ++i) {
            int u, v;
            scanf("%d%d", &u, &v);
            addedge(u, v);
        }
        for (int i = 1; i <= n; ++i)
            if (!dfn[i])
                tarjan(i);
        for (int i = 1; i <= scnt; ++i) {
            for (int j = 0; j < scc[i].size(); ++j)
                printf("%d ", scc[i][j]);
            putchar('\n');
        }
        return 0;
    }

    有啥用啊?

    可以把奇怪的图变成有向无环图(DAG),然后就可以拓扑啥的了。
    然而,Tarjan缩点重新建图的写法我始终没找到。

    来一道模板题的丑陋的代码吧。(LUOGU 2341 受欢迎de奶牛)

    #include <stdio.h>
    #include <cstring>
    #include <cstdlib>
    #include <cmath>
    #include <iostream>
    #include <algorithm>
    using namespace std;
    const int MAXN = 10005;
    const int MAXM = 50005;
    struct Edge {
        int to, nxt;
    } edge[MAXM];
    int n, m, fir[MAXN], dfn[MAXN], low[MAXN], stk[MAXN], top;
    int degree[MAXN], col[MAXN], sum, cnt[MAXN], ans, ecnt, timer;
    void addedge(int u, int v) {
        edge[++ecnt].to = v;
        edge[ecnt].nxt = fir[u];
        fir[u] = ecnt;
    }
    void tarjan(int u) {
        dfn[u] = low[u] = ++timer;
        stk[++top] = u;
        for (int e = fir[u]; e; e = edge[e].nxt) {
            int v = edge[e].to;
            if (!dfn[v]) {
                tarjan(v);
                low[u] = min(low[u], low[v]);
            } else if (!col[v])
                low[u] = min(low[u], dfn[v]);
        }
        if (low[u] == dfn[u]) {
            col[u] = ++sum;
            while (stk[top] != u)
                col[stk[top--]] = sum;
            --top;
        }
    }
    int main() {
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= m; ++i) {
            int u, v;
            scanf("%d%d", &u, &v);
            addedge(u, v);
        }
        for (int i = 1; i <= n; ++i)
            if (!dfn[i])
                tarjan(i);
        for (int u = 1; u <= n; ++u) {
            ++cnt[col[u]];
            for (int e = fir[u]; e; e = edge[e].nxt) {
                int v = edge[e].to;
                if (col[u] != col[v])
                    ++degree[col[u]];
            }
        }
        int temp = 0;
        for (int i = 1; i <= sum; ++i)
            if (degree[i] == 0) {
                ++temp;
                ans = cnt[i];
            }
        if (temp == 1) printf("%d\n", ans);
        else puts("0");
        return 0;
    }

    转载于:https://www.cnblogs.com/herald/p/9830743.html

    展开全文
  • 有向图的强连通分量是由相互均为强连通顶点的最大子集构成的. 强连通分量搜索算法:Kosaraju 首先, 定义有向图GGG的反向图GRG^RGR.由有向图GGG中每一条有向边v−>wv->wv−>w取反的反向边...
  • 有向图的强连通分量 1.强连通 代表的是 这个连通块中的每两个点互相都是有一条路径是可以走到的 2.分量 就是子图; 从这张图上可以看出 A B C这三个点都是互相可以走到的 所以他们就是一个联通块 D E F 三个点都是...
  • 有向图连通分量的Tarjan算法 [有向图连通分量] 在有向图G中,如果两个顶点间至少存在一条路径,称两个顶点强连通(strongly connected)。如果有向图G的每两个顶点都强连通,称G是一个强连通图。非强连通图有向...
  • 对于一个有向图, 连通分量: 对于分量中任意u, v, 必然可以从u走到v, 也可以从v走到u 强(极大)连通分量 极大连通分量. 如果连通分量加上任何一个点之后, 都不是连通分量了, 那么称这个连通分量为极大连通分量(强连通...
  • Tarjan算法求有向图连通分量 常用场景: 求顶点基:求出强连通分量后缩点,得到DAG。在入度为0的点中,每个强连通分量中任取一个点,可构成顶点基。 核心思想: 注意每个节点在一个且仅在一个强连通...
  • 有向图的强连通分量

    2019-09-08 09:44:58
    有向图连通分量:在有向图G中,如果两个顶点vi,vj间(vi>vj)有一条从vi到vj的有向路径,同时还有一条从vj到vi的有向路径,则称两个顶点强连通(strongly connected)。如果有向图G的每两个顶点都强连通,称G是一...
  • 有向图连通分量的Tarjian算法

    千次阅读 2018-08-09 09:51:49
    有向图连通分量的Tarjian算法 2016年08月16日 10:38:45 阅读数:2006 【转载地址】点击打开链接 [有向图连通分量] 在有向图G中,如果两个顶点间至少存在一条路径,称两个顶点强连通(strongly connected)...
  • 有向图连通分量定义:如果一个图中的任意两点在两个方向上都互相连通,则该图为强连通图。极大强连通图为有向图的强连通分量(注意是极大,不是最大。一个图会有多个强连通分量)。感性理解,强连通图就是多个环,...
  • 有向图连通分量:在有向图G中,如果两个顶点间至少存在一条路径,称两个顶点强连通(strongly connected)。 如果有向图G的每两个顶点都强连通,则称G是一个强连通图。 非强连通图有向图的极大强连通子图,成为...
  • 有向图连通分量的Tarjan算法 [有向图连通分量] 在有向图G中,如果两个顶点间至少存在一条路径,称两个顶点强连通(strongly connected)。如果有向图G的每两个顶点都强连通,称G是一个强连通图。非强连通图...
  • 对于一个图,说他是连通的当且仅当从该图的任何一个顶点到该图的另一个顶点都走得通,强连通的意思是,对于一个有向图,任何一个顶点到另外一个顶点都能互通,强连通分量就是极大强连通子图,可以这么理解,对于该图...
  • 有向图中若任意两个顶点都可以到达,则图是强连通的 图的连通分量是顶点在“从......可达”关系下的等价类。即可以理解为其一个子图,所有的连通分量构成图的一个划分。 对于判断无向图连通性,直接用并查集(Union...
  • 缩点之后想一想要不要管重边。时候可以忽略,时候却不行。 ...待更新 转载于:https://www.cnblogs.com/butterflydew/p/9162204.html
  • [有向图连通分量] 在有向图G中,如果两个顶点间至少存在一条路径,称两个顶点强连通(strongly connected)。如果有向图G的每两个顶点都强连通,称G是一个强连通图。非强连通图有向图的极大强连通子图,称为强连通...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 3,883
精华内容 1,553
关键字:

有向图连通分量