P2746 [USACO5.3]校园网Network of Schools
翻译题面：
任务A：求缩点后的图中有多少个点入度为0。
任务B：求入度为0的点数与出度为0的点数的较大值。
注意避免连边时重复算出度入度，所以用set而非vector存图；只有一个点（缩点后）要特判。
写代码时注意定义For的话不能写成 For(j,0,g[i].size()-1)，查了至少30min...
#include <bits/stdc++.h> #define ri register int #define For(i,l,r) for(ri i=l;i<=r;i++) using namespace std; const int M=105; vector<int> g[M]; stack<int> st; set<int> gg[M]; int n,dfn[M],low[M],inst[M],belong[M],in,cnt,indg[M]; inline void tarjan(int x){ low[x]=dfn[x]=++in;st.push(x);inst[x]=1; //For(i,0,g[x].size()-1){ for(int i=0;i<g[x].size();i++){ if(!dfn[g[x][i]]) tarjan(g[x][i]),low[x]=min(low[x],low[g[x][i]]); else if(inst[g[x][i]]) low[x]=min(low[x],dfn[g[x][i]]); } if(dfn[x]==low[x]){ cnt++; while(st.top()!=x){ belong[st.top()]=cnt; inst[st.top()]=0; st.pop(); } belong[st.top()]=cnt; inst[st.top()]=0; st.pop(); } } int main(){ cin>>n; For(i,1,n){int x;while(cin>>x && x)g[i].push_back(x);} For(i,1,n){if(!dfn[i])tarjan(i);} if(cnt==1) {cout<<1<<endl<<0<<endl;return 0;} For(i,1,n){ //For(j,0,g[i].size()-1){ for(int j=0;j<g[i].size();j++){ if(belong[g[i][j]]!=belong[i]&&gg[belong[i]].find(belong[g[i][j]])==gg[belong[i]].end()){ gg[belong[i]].insert(belong[g[i][j]]); indg[belong[g[i][j]]]++; } } } int ans1=0,ans2=0; For(i,1,cnt){ if(indg[i]==0) ans1++; if(gg[i].size()==0) ans2++; } cout<<ans1<<endl<<max(ans1,ans2)<<endl; return 0; }
P3119 [USACO15JAN]草鉴定Grass Cownoisseur
没有逆行就很简单，那么加上逆行之后我是想建一个反向图，新图和原图各跑一遍SPFA求最长边，然而然后就不知道了。
法一.%分%层%图%。
Tarjan缩点+强连通分量不多赘述。
将图复制一遍，点的编号从1~N到（N+1）~（N+N），在两层图中连边。原图上的每条边，从原图指向的点到新图的起始点连一条边（即逆向操作），边权同原边，只能操作一次，所以从上层的图（新图）无法回到下层。最后跑一遍SPFA，节点1所在的强连通分量的编号到节点1所在的强连通分量编号+N上的最长路即所求答案。
#include<bits/stdc++.h> #define For(i,l,r) for(int i=l;i<=r;i++) using namespace std; const int M=1e5+5; const int inf=0x3f3f3f; vector<int> g[M]; vector<int> gg[M<<1]; int n,m,op,in,dfn[M],low[M],bcc[M],siz[M<<1],cnt,dist[M<<1]; bool inst[M<<1]; stack<int>st; queue<int>q; inline void tarjan(int x){ dfn[x]=low[x]=++in;inst[x]=1;st.push(x); for(int i=0;i<g[x].size();i++){ if(!dfn[g[x][i]]) tarjan(g[x][i]),low[x]=min(low[x],low[g[x][i]]); else if(inst[g[x][i]]) low[x]=min(low[x],dfn[g[x][i]]); } if(dfn[x]==low[x]){ cnt++; while(st.top()!=x){ bcc[st.top()]=cnt;inst[st.top()]=0;st.pop();siz[cnt]++; } bcc[st.top()]=cnt;inst[st.top()]=0;st.pop();siz[cnt]++; } } int main(){ scanf("%d%d",&n,&m); while(m--){int u,v; scanf("%d%d",&u,&v);g[u].push_back(v);} For(i,1,n) if(!dfn[i])tarjan(i); For(i,1,cnt)siz[cnt+i]=siz[i]; For(i,1,n){ for(int j=0;j<g[i].size();j++){ if(bcc[i]!=bcc[g[i][j]]){ gg[bcc[i]].push_back(bcc[g[i][j]]); gg[bcc[g[i][j]]].push_back(bcc[i]+cnt); gg[bcc[i]+cnt].push_back(bcc[g[i][j]]+cnt); } } } inst[bcc[1]]=1;q.push(bcc[1]); while(!q.empty()){ int x=q.front(); for(int i=0;i<gg[x].size();i++){ if(dist[gg[x][i]]<dist[x]+siz[x]){ dist[gg[x][i]]=dist[x]+siz[x]; if(!inst[gg[x][i]]) inst[gg[x][i]]=1,q.push(gg[x][i]); } } q.pop();inst[x]=0; } printf("%d ",dist[bcc[1]+cnt]); return 0; }
法二.我“显而易见”（也想了3、5min吧，其实也是比较基础也比较好想的做法）的做法的完整版。
P3225 [HNOI2012]矿场搭建
听说是求割点模板题？分析一下几种情况，这种一看没啥思路的题的基础操作，算是颅内打表
#include<bits/stdc++.h> #define ll long long #define For(i,l,r) for(int i=l;i<=r;i++) using namespace std; int head[505],dfn[505],low[505],vis[505],stack[505]; bool cut[505],in_stack[505]; int n,m,cnt,num,tot,deg,ans1,T,cases,root,top; ll ans2; struct node { int to; int next; }e[1010]; inline void insert(int from,int to) { e[++num].to=to; e[num].next=head[from]; head[from]=num; } inline int read() { int x=0,f=1; char c=getchar(); while (c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while (c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} return x*f; } inline void tarjan(int u,int fa){ dfn[u]=low[u]=++tot; for(int i=head[u];i;i=e[i].next){ int v=e[i].to; if(!dfn[v]){ tarjan(v,u); low[u]=min(low[u],low[v]); if(low[v]>=dfn[u]){ if(u==root) deg++; else cut[u]=1; } } else if(v!=fa) low[u]=min(low[u],dfn[v]); } } inline void dfs(int x){ vis[x]=T; if(cut[x]) return; cnt++; for(int i=head[x];i;i=e[i].next){ int v=e[i].to; if(cut[v]&&vis[v]!=T) num++,vis[v]=T; if(!vis[v]) dfs(v); } } int main() { m=read(); while (m) { memset(head,0,sizeof(head)); memset(dfn,0,sizeof(dfn)); memset(low,0,sizeof(low)); memset(cut,0,sizeof(cut)); memset(vis,0,sizeof(vis)); top=cnt=tot=n=ans1=T=0; ans2=1; For(i,1,m){ int u=read(),v=read(); n=max(n,max(u,v)); insert(u,v),insert(v,u); } For(i,1,n){ if(!dfn[i]) tarjan(root=i,0); if(deg>=2) cut[root]=1; deg=0; } For(i,1,n){ if(!vis[i]&&!cut[i]){ T++;cnt=num=0; dfs(i); if(!num){ ans1+=2; ans2*=cnt*(cnt-1)/2; } if(num==1){ ans1++; ans2*=cnt; } } } printf("Case %d: %d %lld ",++cases,ans1,ans2); m=read(); } return 0; }