Tarjan finds the strongly connected component o (n+m), shrinking point

Tarjan Find the strongly connected component $O(n+m)$ , Shrinkage point

---

I regret not blogging at the beginning

Related video tutorial recommendations ： Mr. Dong , Dirty brother .

Strong connectivity ： If a Directed graph Nodes of can reach each other , The graph is said to be strongly connected .

Strong connected components （SCC）： Maximal strongly connected subgraphs .

---

Pair graph dfs when , Each node is accessed only once , The visited nodes and edges form a search tree .

There are four cases of directed edges ：

1. By the tree ： Access the side that the node goes through . black .
2. Leaseback side ： Point to the edge of the ancestor node . Red .
3. Cross edge ： The grapefruit tree points to the edge of the left sub tree . green .
4. Forward edge ： Point to the edge of the node in the subtree . Blue .

---

Leaseback edge and tree edge must form a ring , The cross edge may form a ring with the edge of the tree , The forward side is useless

---

If node X Is a strongly connected component in Search tree The first node encountered in , said X Is the root of this strongly connected component .

1. Time stamp $dfn[]$ ： node X The order of the first visit .
2. Retroactive value $low[]$： From the node X set out , The earliest timestamp that can be accessed .

int dfn[N],low[N],cnt;
vector<int>scc,tot;
int stk[N],top,siz[N];// Stack , To the top of the stack , Some SCC Number of nodes 
bool instk[N];
//  Enter into 、 return 、 leave 、 In the third part of .
void tarjan(int x){
    
    // x 【 Enter into 】 Stack , affix one's seal 
    dfn[x] = low[x] = ++cnt;
    stk[++top] = x;
    instk[x] = 1;
    
    //  Traverse  x  Adjacency point ,【 return 】X
    for(int i=h[x];~i;i=ne[i]){
    
        int j = e[i];
        if(!dfn[j]){
    
            tarjan(j);
            low[x] = min(low[x],low[j]); //  If j There is a atavism , You need to update low[x]
        }
        else if(instk[j]){
     // j Has been accessed and is already on the stack , Horizontal cross edge and atavism edge 
            low[x] = min(low[x],dfn[j]);
        }
	}
    // 【 leave 】 open X, Record SCC
    if(dfn[x] == low[x]){
     // x  It's some one SCC The root node 
        int y; tot++;
        do{
    
            y = stk[top--];instk[y]=0;
            scc[tot].pb(y);
            siz[tot]++;
        }while(y!=x);
    }
}

---

Never thought about the problem

1. Why would there be $low[]$ ？

low[x] = min(low[x],low[y])  If you remove it , Traverse to the lowest node , When you want to return through your ancestors , It will be regarded as one in advance SCC Out of the stack .

2. $low[x] = min(low[x],dfn[y]) $ Can be replaced by $low[y]$ Do you ？

seek $SCC$ It can be changed , But please The double connected component of the undirected edge will go wrong . therefore Don't change ！

---

P3387 【 Templates 】 Shrinkage point

Finally, the pit was filled

Drawing -> tarjan seek SCC -> new SCC Between them -> topsort -> Traversal is the most valuable .

 At the beginning, I also thought about the dots and SCC Even the edge , Thief chaos , There is only 60 branch .
 There is also a direct in topsort in dp.
for(int i=1;i<=n;i++)
{
    
    for(int j=h[i];~j;j=ne[j])
    {
    
        int y=e[j];
        if(id[i]==id[y])continue;
        adds(id[i],id[y]);
        //  Connect edges directly between new connected components .
        d[id[y]]++;
    }
}

// Problem: P3387 【 Templates 】 Shrinkage point 
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3387
// Memory Limit: 125 MB
// Time Limit: 1000 ms

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <queue>
#include <set>
#include <map>
#include <vector>
#include <sstream>
#define pb push_back 
#define in insert
#define mem(f, x) memset(f,x,sizeof(f)) 
#define fo(i,a,n) for(int i=(a);i<=(n);++i)
#define fo_(i,a,n) for(int i=(a);i<(n);++i)
#define debug(x) cout<<#x<<":"<<x<<endl;
#define endl '\n'
using namespace std;

template<typename T>
ostream& operator<<(ostream& os,const vector<T>&v){
    for(int i=0,j=0;i<v.size();i++,j++)if(j>=5){
    j=0;puts("");}else os<<v[i]<<" ";return os;}
template<typename T>
ostream& operator<<(ostream& os,const set<T>&v){
    for(auto c:v)os<<c<<" ";return os;}

typedef pair<int,int>PII;
typedef pair<long,long>PLL;

typedef long long ll;
typedef unsigned long long ull; 
const int N=2e5+10,M=1e5+10;
int n,m;
int w[N];// Weight before shrinking point 

int h[N],e[N],ne[N],idx;
int hs[N],es[N],nes[N],idxs;

int dfn[N],low[N],tim;
int stack[N],top;
bool is_in[N];

int cnt;// Storage SCC Number 
int id[N]; //  Where is each node stored SCC in 
vector<int>scc[N];
int W[N];// Weight after shrinking point 

void add(int a,int b){
    
	e[idx]=b,ne[idx]=h[a],h[a]=idx++;	
}

void adds(int a,int b){
    
	es[idxs]=b,nes[idxs]=hs[a],hs[a]=idxs++;	
}

void tarjan(int u){
    
	dfn[u]=low[u]=++tim;
	stack[++top]=u;
	is_in[u]=1;
	for(int i=h[u];~i;i=ne[i]){
    
		int j=e[i];
		if(!dfn[j]){
    
			tarjan(j);
			low[u]=min(low[u],low[j]);
		}
		else if(is_in[j]){
    
			low[u]=min(low[u],dfn[j]);
		}
	}
	if(dfn[u]==low[u]){
    
		int y;
		cnt++;
		do{
    
			y=stack[top--];
			is_in[y]=false;
			scc[cnt].pb(y);
			W[cnt]+=w[y];
			id[y]=cnt;	
		}while(u!=y);
	}
}

int d[N],Topo[N];
int Cnt;// Topological order subscript 
ll dis[N];

void topo()
{
    
	queue<int>que;
	for(int i=1;i<=cnt;i++)
		if(!d[i]){
    
			que.push(i);
			Topo[++Cnt]=i;
			dis[i] = W[i];
		}
	while(que.size())
	{
    
		int t=que.front();
		que.pop();
		for(int i=hs[t];~i;i=nes[i])
		{
    
			int j=es[i];
			d[j]--;
			if(!d[j])
			{
    
				que.push(j);
				dis[j] = max(dis[j] , dis[t] + W[j]);
				Topo[++Cnt]=j;
			}
		}

	}
}

void solve()
{
    
	mem(h,-1);
	mem(hs,-1);
	cin>>n>>m;
	fo(i,1,n)cin>>w[i];
	fo(i,1,m){
    
		int a,b;cin>>a>>b;
		add(a,b);
	}
	for(int i=1;i<=n;i++)
		if(!dfn[i])
			tarjan(i);
	
	for(int i=1;i<=n;i++)
	{
    
		for(int j=h[i];~j;j=ne[j])
		{
    
			int y=e[j];
			if(id[i]==id[y])continue;
			adds(id[i],id[y]);
			//  Connect edges directly between new connected components .
			d[id[y]]++;
		}
	}
	topo();
	
	ll ans = 0;
	fo(i,1,Cnt){
    
		ans = max(ans,dis[i]);
	}
	cout<<ans<<endl;
}

int main()
{
    
	solve();
	return 0;
}

P2341 [USACO03FALL / HAOI2006] Popular cattle G

Title Description

Every cow dreams of being a star in the cowshed . The cow that all cows like is a star cow . All cows are narcissists , Every cow always likes its own . Between cows “ like ” It can be transmitted —— If $A$ like $B$,$B$ like $C$, that $A$ I also like $C$. It's in the bullpen $N$ A cow , Given some of the relationships between cows , Please figure out how many cows can be stars .

Input format

first line ： Two integers separated by spaces ：$N$ and $M$.

Next $M$ That's ok ： Two integers separated by spaces on each line ：$A$ and $B$, Express $A$ like $B$.

about $100\%$ The data of ,$1\le N\le 10^4$,$1\le M\le 5\times 10^4$.

Output format

A single integer in a row , The number of star cows .

---

Easy to find , only one SCC Maybe the answer is . Then I thought about shrinking （ No need to build a map ） Statistics SCC The degree of , Dangru == cnt-1 Statistical answer , If more than one condition is met ans = 0.

Then be hack 了

Because maybe SCC There is indirect penetration . So we should calculate the degree .AC！

// Problem: P3387 【 Templates 】 Shrinkage point 
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3387
// Memory Limit: 125 MB
// Time Limit: 1000 ms

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <queue>
#include <set>
#include <map>
#include <vector>
#include <sstream>
#define pb push_back 
#define in insert
#define mem(f, x) memset(f,x,sizeof(f)) 
#define fo(i,a,n) for(int i=(a);i<=(n);++i)
#define fo_(i,a,n) for(int i=(a);i<(n);++i)
#define debug(x) cout<<#x<<":"<<x<<endl;
#define endl '\n'
using namespace std;

template<typename T>
ostream& operator<<(ostream& os,const vector<T>&v){
    for(int i=0,j=0;i<v.size();i++,j++)if(j>=5){
    j=0;puts("");}else os<<v[i]<<" ";return os;}
template<typename T>
ostream& operator<<(ostream& os,const set<T>&v){
    for(auto c:v)os<<c<<" ";return os;}

typedef pair<int,int>PII;
typedef pair<long,long>PLL;

typedef long long ll;
typedef unsigned long long ull; 
const int N=1e4+10,M=1e5+10;
int n,m;
int h[N],e[10*N],ne[10*N],idx;
vector<int>scc[N];
int sz[N],cnt;// Storage SCC Number 
int dfn[N],low[N],tim;
int stack[N],top;
int id[N],d[N];
bool is_in[N];

void tarjan(int u){
    
	dfn[u] = low[u] = ++tim;
	stack[top++] = u;
	is_in[u] = true;
	for(int i=h[u];i!=-1;i=ne[i]){
    
		int v = e[i];
		if(!dfn[v]){
    
			tarjan(v);
			low[u] = min(low[u],low[v]);
		}
		else if(is_in[v])
			low[u] = min(low[u],dfn[v]);
	}
	if(dfn[u] == low[u]){
    
		int v;
		cnt++;
		do{
    
			v = stack[--top];
			is_in[v] = false;
			scc[cnt].pb(v);
			sz[cnt]++;
			id[v] = cnt;
		}while(v != u);
	}
}

void add(int a,int b){
    
	e[idx]=b,ne[idx]=h[a],h[a]=idx++;	
}

void solve(){
    
	mem(h,-1);
	cin>>n>>m;
	fo(i,1,m){
    
		int a,b;cin>>a>>b;
		add(a,b);
	}
	for(int i=1;i<=n;i++){
    
		if(!dfn[i]){
    
			tarjan(i);
		}
	}
	for(int i=1;i<=n;i++){
    
		for(int k=h[i];~k;k=ne[k]){
    
			int j=e[k];
			if(id[i] == id[j])continue;
			d[id[i]]++;
		}
	}
	ll ans = 0;
	int num = 0;
	fo(i,1,cnt){
    
		if(!d[i]){
    
			num++;
			ans += sz[i];
		}
	}
	if(num>1)ans = 0;
	cout<<ans;
}

int main()
{
    
	solve();
	return 0;
}

Picking mushrooms ( Shrink Point Application topo The longest way （ With edge weight and point weight ） + card double precision ！)

Title Description

Xiao Pang and ZYR Want to go ESQMS The forest gathers mushrooms .

ESQMS There are... In the forest $N$ A little Bush ,$M$ A path , Every path is one-way , Connect two small trees , There's a certain amount of mushrooms on it . Xiao Pang and ZYR Pass a path once , You can pick all the mushrooms on this road . because ESQMS The forest is a magical fertile land , So the mushrooms on a road were picked , Some new mushrooms will grow , The number is the number of mushrooms multiplied by the number of this road “ Coefficient of recovery ”, Round down again .

such as , There are... On one road $4$ A mushroom , This road is “ Coefficient of recovery ” by $0.7$, Then first ~ The number of mushrooms that can be collected through this path four times is $4,2,1,0$.

Now? , Xiao Pang and ZYR from $S$ Start from the small trees on the th , Ask them how many mushrooms they can pick at most .

Input format

The first line has two integers ,$N$ and $M$.

Line two to line two $M+1$ That's ok , Four numbers per line , Each represents the starting point of a path , End , Initial mushroom number , Coefficient of recovery .

The first $M+2$ That's ok , An integer $S$.

Output format

One line, one integer , It indicates how many mushrooms can be picked at most , Make sure the answer doesn't exceed $(2^{31}-1)$.

The sample input

3 3
1 2 4 0.5
1 3 7 0.1
2 3 4 0.6
1

Sample output

8

about $100\%$ The data of ,$1\le N\le 8\times 10^4$,$1\le M\le 2\times 10^5$,$0\le \text{Coefficient of recovery}\le 0.8$ And there is at most one decimal , $1\le S\le N$.

---

The only difference between the point weight and the longest path board is that the point weight becomes the edge weight . Shrinkage point , For each SCC Violence demands his internal side power and records it as his point power . And then run Topo Seeking the longest way .

Finally brought up the sample , Full of confidence , Send it up 10 branch qwq

And finally 30 Divide up , Want to see the sample 1 I found that the code was garbled ？！？ With the help of Guyou and management, I got the sample 1 The data of , The tablet can actually see the correct data . I found that I first * 10 Read it again , It's numb .

The accuracy of this question card , You need to take 10 Again /10, There is no need to read in the whole process double！

There is also how to use topological sorting dp.

Find the longest path by topology

The initial point is different 0 Read in point , Put him in first , Other zero entry points also enter , And then initially become -0x3f3f3f3f .

topo When , Update all critical points , You can't update it inside ！

void topo()
{
    
	queue<int>que;
	for(int i=1;i<=cnt;i++){
    
		if(!d[i]){
    
			que.push(i);
		}
		dis[i] = -0x3f3f3f3f3f3f3f3f;
	}
	
	root = id[root];
	dis[root] = W[root];	
	
	while(que.size()){
    
		int t=que.front();
		que.pop();
		for(int i=hs[t];~i;i=nes[i])
		{
    
			int j=es[i];
			int edge_value = Ws[i];
			// ?  discharge if It's different inside and outside  ,  Be sure to put takeout , Inside wa！
			dis[j] = max(dis[j] , dis[t] + W[j] + edge_value);
			d[j]--;
			if(!d[j]){
    
				que.push(j);
			}
		}

	}
}

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <queue>
#include <set>
#include <map>
#include <vector>
#include <sstream>
#define pb push_back 
#define in insert
#define mem(f, x) memset(f,x,sizeof(f)) 
#define fo(i,a,n) for(int i=(a);i<=(n);++i)
#define fo_(i,a,n) for(int i=(a);i<(n);++i)
#define debug(x) cout<<#x<<":"<<x<<endl;
#define endl '\n'
using namespace std;

typedef long long ll;
typedef unsigned long long ull; 
const int N=2e5+10,M=1e5+10;
int n,m;

int h[N],e[N],ne[N],w[N],idx,p[N];
int hs[N],es[N],nes[N],idxs;
int Ws[N];

int dfn[N],low[N],tim;
int stack[N],top;
bool is_in[N];

int cnt;// Storage SCC Number 
int id[N]; //  Where is each node stored SCC in 
vector<int>scc[N];
int W[N];// Weight after shrinking point 
int root;

void add(int a,int b,int c,int d){
    
	e[idx]=b,ne[idx]=h[a],w[idx]=c,p[idx]=d,h[a]=idx++;	
}

void adds(int a,int b,int c){
    
	es[idxs]=b,nes[idxs]=hs[a];
	Ws[idxs]=c;
	hs[a]=idxs++;	
}

void tarjan(int u){
    
	dfn[u]=low[u]=++tim;
	stack[++top]=u;
	is_in[u]=1;
	for(int i=h[u];~i;i=ne[i]){
    
		int j=e[i];
		if(!dfn[j]){
    
			tarjan(j);
			low[u]=min(low[u],low[j]);
		}
		else if(is_in[j]){
    
			low[u]=min(low[u],dfn[j]);
		}
	}
	if(dfn[u]==low[u]){
    
		int y;
		cnt++;
		do{
    
			y=stack[top--];
			is_in[y]=false;
			scc[cnt].pb(y);
			id[y]=cnt;	
		}while(u!=y);

	}
}

int d[N];
ll dis[N];

void topo()
{
    
	queue<int>que;
	for(int i=1;i<=cnt;i++){
    
		if(!d[i]){
    
			que.push(i);
		}
		dis[i] = -0x3f3f3f3f3f3f3f3f;
	}
	
	root = id[root];
	dis[root] = W[root];	
	
	while(que.size()){
    
		int t=que.front();
		que.pop();
		for(int i=hs[t];~i;i=nes[i])
		{
    
			int j=es[i];
			int edge_value = Ws[i];
			// ?  discharge if It's different inside and outside  ,  Be sure to put takeout , Inside wa！
			dis[j] = max(dis[j] , dis[t] + W[j] + edge_value);
			d[j]--;
			if(!d[j]){
    
				que.push(j);
			}
		}

	}
}

void solve()
{
    
	mem(h,-1);
	mem(hs,-1);
	cin>>n>>m;
	fo(i,1,m){
    
		int a,b,c;
		double d;
		cin>>a>>b>>c>>d;
		d*=10;
		add(a,b,c,d);
	}
	cin>>root;
	for(int i=1;i<=n;i++)
		if(!dfn[i])
			tarjan(i);
	for(int i=1;i<=n;i++)
	{
    
		for(int j=h[i];~j;j=ne[j])
		{
    
			int y=e[j];
			int value=w[j];
			int cost=p[j];
			ll sum = 0;
			
			if(id[i]==id[y]){
    
				// i,y value
				while(value){
    
					sum += value;
					value = value*cost/10;
				}	
				W[id[i]] += sum;
				continue;
			}

			adds(id[i],id[y],value); //  I can only walk once 
			d[id[y]]++;
			//  Connect edges directly between new connected components .
		}
	}
	topo();
	
	ll ans = 0;
	fo(i,1,cnt){
    
		ans = max(ans,dis[i]);
	}
	cout<<ans<<endl;
}

int main()
{
    
	solve();
	return 0;
}