洛谷 P2863 [USACO06JAN]牛的舞会The Cow Prom-强连通分量(Tarjan)

本来分好组之后，就确定好了每个人要学什么，我去学数据结构啊。

因为前一段时间遇到一道题是用Lca写的，不会，就去学。

然后发现Lca分为在线算法和离线算法，在线算法有含RMQ的ST算法，前面的博客也写了。离线算法是基于DFS的Tarjan算法。

然后就打算去学一下Tarjan，因为以前也看过但是没看完，就打算学一下，因为Tarjan算法是图论的内容，然后就让图论选手教了我一下大环套小环的怎么推，然后就尴尬了。

我是学数据结构的，没有要去抢图论的内容学。。。

我也看了线段树了啊。

学完这个Tarjan我就溜。

气氛有些微妙。。。

好了，继续，反正脸皮厚，今天打电话习惯性被怼，打完电话整个人都不好了，我是垃圾哦，不好意思。

写题写题，无所谓了。

P2863 [USACO06JAN]牛的舞会The Cow Prom

https://www.luogu.org/problemnew/show/P2863

这个题就是问能不能成连通的，就是强连通分量啊，用Tarjan写，然后判断一下，如果强连通里面的数的个数大于等于2就可以了。问有几个是满足条件的。

Tarjan裸模板题。

代码:

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 #include<cstdlib>
 6 #include<algorithm>
 7 using namespace std;
 8 #define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
 9 const int maxn=5e4+10;
10 struct node{
11     int v,next;
12 }edge[maxn];
13 int DFN[maxn],LOW[maxn];
14 int stack[maxn],heads[maxn],visit[maxn],cnt,tot,indexx,num;
15 void add(int x,int y){
16     edge[++cnt].next=heads[x];
17     edge[cnt].v=y;
18     heads[x]=cnt;
19     return ;
20 }
21 void tarjan(int x){
22     DFN[x]=LOW[x]=++tot;
23     stack[++indexx]=x;
24     visit[x]=1;
25     for(int i=heads[x];i!=-1;i=edge[i].next){
26         if(!DFN[edge[i].v]){
27             tarjan(edge[i].v);
28             LOW[x]=min(LOW[x],LOW[edge[i].v]);
29         }
30         else if(visit[edge[i].v]){
31             LOW[x]=min(LOW[x],DFN[edge[i].v]);
32         }
33     }
34     if(LOW[x]==DFN[x]){    
35             int cnt=0;
36         do{
37             cnt++;
38             //printf("%d ",stack[indexx]);
39             visit[stack[indexx]]=0;                           //indexx是记录模拟栈的长度
40             indexx--;
41         }while(x!=stack[indexx+1]);//出栈，并且输出。
42          //printf("
");
43          if(cnt>=2)num++;                                     //cnt就是判断一下条件
44     }
45     return ;
46 }
47 int main(){
48     memset(heads,-1,sizeof(heads));
49     int n,m;
50     ios;
51     cin>>n>>m;
52     int x,y;
53     for(int i=1;i<=m;i++){
54         cin>>x>>y;
55         add(x,y);
56     }
57     num=0;
58     for(int i=1;i<=n;i++)
59         if(!DFN[i])tarjan(i);
60     cout<<num<<endl;
61     return 0;
62 }

写完了，溜了。