CCF 201509-4 Expressway

subject

Problem description

　　 A state n Cities , In order to make the traffic between cities more convenient , The king of the country is going to build some highways between the cities , Due to financial constraints , In the first phase, the king plans to build some one-way highways between some cities .
　　 Now? , The ministers made a plan for the king to build a highway . After reading the plan , The king found out , Some cities can go directly through highways （ Not through other cities ） Or indirectly （ Through one or more other cities ） arrive , And some can't . If the city A You can get to the city by motorway B, And the city B You can also get to the city by highway A, Then these two cities are called convenient cities .
　　 The king wants to know , In the plan the ministers gave him , How many convenient cities are there .

Input format

　　 The first line of input contains two integers n, m, They are the number of cities and one-way highways .
　　 Next m That's ok , Two integers per line a, b, Representing City a There is a one-way highway connecting the city b.

Output format

　　 Output one line , Contains an integer , Number of convenient city pairs .

The sample input

5 5
1 2
2 3
3 4
4 2
3 5

Sample output

3

Sample explanation

　　 The connection between cities is shown in the figure . Yes 3 A convenient city is right , They are (2, 3), (2, 4), (3, 4), Please note that (2, 3) and (3, 2) To see the same convenient city .

Evaluate use case size and conventions

　　 front 30% The evaluation use case of meets 1 ≤ n ≤ 100, 1 ≤ m ≤ 1000;
　　 front 60% The evaluation use case of meets 1 ≤ n ≤ 1000, 1 ≤ m ≤ 10000;
　　 All evaluation cases meet 1 ≤ n ≤ 10000, 1 ≤ m ≤ 100000.

---

Problem analysis

It's not difficult to find that the inspection point is Strongly connected branch . If there is a slave path u→v And path v→u, be (u,v) For the convenience of the city , Obviously, every such convenient city corresponds to 2 All points are in the same strongly connected branch , So the problem is to find all the strongly connected branches in the input graph , This problem does not need to know which points in each strongly connected branch , You only need to know how many points each strongly connected branch contains .

After finding the number of points contained in each strongly connected branch , For each Strongly connected branches N For one thing , Any of them 2 A point pair consisting of points is a convenient city pair , So it's combinatorial number C(N,2) = N * (N-1) / 2. Last , Adding the convenient city logarithms of each strongly connected branch together is the final result .

The main idea of the problem is analyzed clearly , Here is the key to finding strongly connected branches , What we use here is Tarjan Algorithm , Can be said to be DFS An application of , However, it is difficult to understand directly , It's suggested to know about Kosaraju Algorithm , This is easy to understand , And some core ideas （Low[] and DFN[] The actual meaning of ） It's the same , It's just Kosaraju The algorithm needs to pass twice DFS, and Tarjan The algorithm only needs one time , therefore Tarjan The algorithm is more efficient .

---

About Tarjan Algorithm Low[] and DFN[] The calculation of is described here ：

Low(u) = min
{
    DFN[u],// situation 1
    Low[v],// situation 2
    DFN[back]// situation 3
}

DFN[] It means that each point is in this DFS Access order in . and Low You need to choose the minimum in three cases ：

1. Its own DFN Serial number .

2. Of all the Forward edge （forward edge）<u,v> All of the v in , The smallest Low[v]. The so-called forward side <u,v>, Refer to DFS China first visited u Then go deeper and visit v also v Have not been visited , That is, in the depth first search spanning tree .

3. Of all the Back to the side （back edge）<v,pre> All of the pre in , The smallest DFN[pre]. The so-called back <v,pre>, Refer to DFS China first visited v Then go deeper and visit pre however pre Has been visited before , That is, in the depth first search spanning tree pre yes v Our ancestors also exist on the edge <v,pre>.

Although it can be calculated from the above description , But it still seems obscure , So it is illustrated and intuitively represented by the figure DFN[] and Low[] The meaning of ：

  To the above figure, from A Point start depth first search , Get a depth first search spanning tree, as shown in the following figure

Each node i The first number of indicates DFN[i], Obviously it is DFS The traversal order of , The second number means Low[i], To understand its meaning , First describe . The black edge is the forward edge described before （forward edge）, The gray edge is the back edge described before （back edge）.

Pass the above figure Low[i] The meaning of is more obvious ,Low[i] Indicates in the depth first search spanning tree from i Starting to walk down or up the path has the smallest DFN The node of , But the requirement is You can only go back one way at most （ Gray edge ）, Such as Low[E] Is through the path E→F→D It has reached the minimum that can be reached DFN The node of D（ Because you can only go back one way at most , So we can't start from D→A）.

thus , Every DFN=Low The node of It's just one. Strongly connected branch Of Separation point 了 , As shown in figure of A and D.

Add why it passed 3 In this case Low[i] It is the smallest that can be reached DFN The node of ：

situation 1 Obviously, it is the most basic , situation 2 And circumstances 3 Calculated Low It can only be less than the case 1. For the situation 2, Let the forward edge be <u,v>, If Low[v]<Low[u], It means v Can be reached with smaller DFN The node of , So at this time, we should make Low[u] =Low[v]（ It can be combined with D→E Look at ）. For the situation 3, If there is a back side <v,pre>, Then it is obvious that we can return to the peak of DFN It is also the smallest that can be achieved DFN One of the candidate nodes （ It can be combined with the above figure D→A Look at ）. Take the smallest of the three .

---

After explaining a lot, I finally explained the meaning of these two arrays , About Tarjan The algorithm is still hard to understand , I suggest you take a look Kosaraju Algorithm , By the above description Kosaraju The algorithm should be very clear （《 Data structure and algorithm analysis ——C Language description 》 In the DFS The algorithm of finding strongly connected branches in the application of is Kosaraju Algorithm , Its description is more detailed , Those who have this book can read , It means that this book is really a qualitative change book of data structure for me ）,Tarjan The algorithm seems to be right Kosaraju Algorithm improvement .

There is also a small hole, that is, don't forget For each Unreached vertex execution Tarjan Algorithm , Because the input diagram may consist of several Isolate each other The subgraph of = =, If you forget this, you can only take 80 branch , I won't tell you that I use this problem repeatedly to remove the out degree or in degree as 0 The algorithm of points can finally get 70 Points of = =（ Of course, this algorithm is wrong ）.

Here is the code , Because there are many points , So using Adjacency table method Storage map . Because recently I want to get familiar with STL, So many places use some unnecessary STL, For example, some vector Array can be used to replace , This is just to avoid wasting space and personal proficiency practice , It's no problem to replace it with an array , Then you will find out Tarjan The parameter of the function is just a point = =. The annotated part can record the number of points contained in each strongly connected branch , But the topic does not need to be recorded , So comment it out . Another point is that you can use DFN[] To two or morethings visited[] The role of , because DFN[] Initialize to 0, be DFN[x] by 0 Can mean visited[x]=false, But that's right DFN The assignment of should be from 1 Start not from 0 Start , My code still uses visited[] And right DFN The assignment of is from 0 At the beginning .

Code

#include<cstdio>
#include<vector>
#include<stack>
using namespace std;

stack<int> s;
int cnt = 0,ans = 0;

void Tarjan(const vector<vector<int> > &Vertexs,int From,vector<bool> &visited,vector<int> &DFN,vector<int> &Low,vector<bool> &InStack){
	int To,top;
	s.push(From);
	InStack[From] = true;
	DFN[From] = Low[From] = cnt++;
	
	for(vector<int>::const_iterator it = Vertexs[From].begin();it!=Vertexs[From].end();it++){// Ergodic point From All the adjacency points of To 
		To = *it;
		if(!visited[To]){//(From,To) by forward edge 
			visited[To] = true;
			Tarjan(Vertexs,To,visited,DFN,Low,InStack);
			Low[From] = min(Low[From],Low[To]);// to update Low[]
		}
		else if(InStack[To]){// Already in the stack ,(From,To) by back edge 
			Low[From] = min(Low[From],DFN[To]);
		}
	}
	
	if(DFN[From]==Low[From]){// Roots of strongly connected branches  
		int sum = 1;// Count the number of connected branches  
		top = s.top();
		s.pop();
		InStack[top] = false;
		while(top!=From){
			top = s.top();
			s.pop();
			InStack[top] = false;
			sum++;
		}
		ans += (sum - 1) * sum / 2;
	}
}

int main(){
	int n,m,t1,t2;
	scanf("%d %d",&n,&m);
	vector<vector<int> > Vertexs(n+1);// Adjacency list ,0 Unit No. is vacant 
	// be used for Tarjan Some quantities of the algorithm ： 
	vector<bool> visited(n+1,false);
	vector<bool> InStack(n+1,false);// Whether the record point is in the stack  
	vector<int> DFN(n+1);// Depth first traversal sequence number  
	vector<int> Low(n+1);// Through many forward edge、 at most 1 strip back edge The smallest reachable point DFN 
	//End
	
	for(int i=0;i<m;i++){
		scanf("%d %d",&t1,&t2);
		Vertexs[t1].push_back(t2);
	}
	for(int i=1;i<=n;i++)
		if(!visited[i])
			Tarjan(Vertexs,i,visited,DFN,Low,InStack);// utilize 1 Time DFS An algorithm for finding strongly connected branches  
	
	printf("%d\n",ans);// Each vertex pair in the connected branch is a convenient city pair  
	
	return 0;
}