今天学了一个强连通分量，用tarjan做。北京之前讲过，今天讲完和之前一样，没有什么进步。上课没听讲，只好回来搞，这里安利一个博客：链接
https://blog.csdn.net/qq_34374664/article/details/77488976
讲一下我自己的体会吧，其实就是维护一个栈，然后树上跑dfs，每个节点存两个值：dn和low，dn代表dfs的顺序（时间），low代表的是他可以连通的最小的节点。
模拟一下，然后就会发现，其实整个算法就是模拟了一下将每个点压入栈。然后遇到之前在栈里的元素，向后弹出到这一位就行了。
洛谷板子题：链接
直接上代码，很好懂。
#include<cstdio> #include<iostream> #include<cstring> #include<algorithm> using namespace std; int m,n,len = 0,stc[50050]; int ri = 0,tot = 0,ans = 0; int num[50005]; struct node{ int l,r,nxt; }a[50050]; int low[50050],lst[50050]; int dn[50080]; int chu[50050]; bool vis[50050]; int add(int x,int y) { a[++len].l = x; a[len].r = y; a[len].nxt = lst[x]; lst[x] = len; chu[x]++; } void dfs(int x) { dn[x] = low[x] = ++tot; stc[++ri] = x; vis[x] = 1; for(int k = lst[x];k;k = a[k].nxt) { int y = a[k].r; if(!dn[y]) { dfs(y); low[x] = min(low[x],low[y]); } else if(vis[y]) { low[x] = min(low[x],dn[y]); } } if(low[x] == dn[x]) { ans ++; int v; do { num[ans]++; vis[stc[ri]] = 0; v = stc[ri--]; } while(x != v); } } int main() { memset(vis,0,sizeof(vis)); scanf("%d%d",&n,&m); int x,y; for(int i = 1;i <= m;i++) { scanf("%d%d",&x,&y); add(x,y); } for(int i = 1;i <= n;i++) if(dn[i] == 0) { dfs(i); } // cout<<ans<<endl; tot = 0; for(int i = 1;i <= ans;i++) { if(num[i] > 1) { tot++; } } printf("%d ",tot); return 0; }
洛谷日推了一道题，也是板子，写一下：
每头奶牛都梦想成为牛棚里的明星。被所有奶牛喜欢的奶牛就是一头明星奶牛。所有奶 牛都是自恋狂，每头奶牛总是喜欢自己的。奶牛之间的“喜欢”是可以传递的——如果A喜 欢B，B喜欢C，那么A也喜欢C。牛栏里共有N 头奶牛，给定一些奶牛之间的爱慕关系，请你 算出有多少头奶牛可以当明星。 输入输出格式 输入格式： 第一行：两个用空格分开的整数：N和M 第二行到第M + 1行：每行两个用空格分开的整数：A和B，表示A喜欢B 输出格式： 第一行：单独一个整数，表示明星奶牛的数量 输入输出样例 输入样例#1： 复制 3 3 1 2 2 1 2 3 输出样例#1： 复制 1
直接上代码：
#include<iostream> #include<cstdio> #include<cstring> using namespace std; template <class T> void read(T &x) { char c; bool op = 0; while(c = getchar(),c < '0' || c > '9') if(c == '-' ) op = 1; x = c - '0'; while(c = getchar(),c >= '0' && c <= '9') x =x * 10 + c - '0'; if(op) x = -x; } int lst[50010],dfn[50010],low[50010],n,m,tot = 0,str[50010],top = 0,vis[50010]; int num[50010],chu[50010],col[50010],len,ans; struct node{ int l,r,nxt; }a[50010]; void add(int x,int y) { a[++len].l = x; a[len].r = y; a[len].nxt = lst[x]; lst[x] =len; // chu[x]++; } void tarjan(int x) { dfn[x] = low[x] = ++tot; str[++top] = x; vis[x] = 1; for(int k = lst[x];k;k = a[k].nxt) { int y = a[k].r; if(!dfn[y]) { tarjan(y); low[x] = min(low[x],low[y]); } else if(vis[y]) { low[x] = min(low[x],dfn[y]); } } if(low[x] == dfn[x]) { ans++; int v; do { num[ans]++; vis[str[top]] = 0; v = str[top--]; col[v] = ans; } while(x != v); } } int main() { read(n);read(m); for(int i = 1;i <= m;i++) { int x,y; read(x);read(y); add(x,y); } for(int i = 1;i <= n;i++) { if(dfn[i] == 0) { tarjan(i); } } for(int i = 1;i <= n;i++) { for(int k = lst[i];k;k = a[k].nxt) { if(col[a[k].l] != col[a[k].r]) { chu[col[a[k].l]]++; } } } int tot= 0,f; for(int i = 1;i <= ans;i++) { if(chu[i] == 0) { tot++; f = i; } if(tot >= 2) { puts("0"); return 0; } } printf("%d ",num[f]); return 0; }