HDU2767 ：求一个有向图最少加几条边变成连通图(难度1.5)
HDU3836：（同2767）
HDU4635 ：求一个有向图最多能加几条边，使得加后也不出现自环，重边，强连通分量（难度3+数学，贪心）
HDU5934 ：缩点后找祖先，对每个祖先，如果是一个点就引爆它，是一个缩点，就引爆里面最小代价点。（难度2）
HDU4612 ：求树的直径（难度2.5）
HDU3639 ：缩点+反向（难度2.5）
HDU4587：割点的变形（难度2.5）
2767
2767
HDU2767 #include <iostream> #include <vector> #include <stack> #include <cstring> #include <cstdio> #include <memory.h> using namespace std; const int maxn=20010; int vis[maxn],scc[maxn],scc_cnt,n,m; int ru[maxn],chu[maxn]; vector<int>G[maxn]; vector<int>G2[maxn]; vector<int>S; void _dfs1(int v) { if(vis[v]) return ; vis[v]=1; for(int i=0;i<G[v].size();i++) _dfs1(G[v][i]); S.push_back(v); } void _dfs2(int v) { if(scc[v]) return ; scc[v]=scc_cnt; for(int i=0;i<G2[v].size();i++){ if(!scc[G2[v][i]]) _dfs2(G2[v][i]); } } void find_scc() { S.clear(); for(int i=1;i<=n;i++) _dfs1(i); for(int i=n-1;i>=0;i--) if(!scc[S[i]]){ scc_cnt++;_dfs2(S[i]); } } int main() { int T,i,j,u,v,a,b; scanf("%d",&T); while(T--){ scanf("%d%d",&n,&m); scc_cnt=0;a=b=0; memset(vis,0,sizeof(vis)); memset(scc,0,sizeof(scc)); for(i=1;i<=n;i++){ G[i].clear(); G2[i].clear(); ru[i]=chu[i]=1; } for(i=0;i<m;i++){ scanf("%d%d",&u,&v); G[u].push_back(v); G2[v].push_back(u); } find_scc(); for(u=1;u<=n;u++){ int L=G[u].size(); for(j=0;j<L;j++){ v=G[u][j]; if(scc[u]!=scc[v]) chu[scc[u]]=ru[scc[v]]=0; } } for(i=1;i<=scc_cnt;i++){ if(ru[i]) a++; if(chu[i]) b++; } if(b>a) a=b; if(scc_cnt==1) a=0; printf("%d ",a); } return 0; }
#include <iostream>
#include <vector>
#include <stack>
#include <cstring>
#include <cstdio>
#include <memory.h>
using namespace std;
const int maxn=20010;
int vis[maxn],scc[maxn],scc_cnt,n,m;
int ru[maxn],chu[maxn];
vector<int>G[maxn];
vector<int>G2[maxn];
vector<int>S;
void _dfs1(int v)
{
if(vis[v]) return ;
vis[v]=1;
for(int i=0;i<G[v].size();i++) _dfs1(G[v][i]);
S.push_back(v);
}
void _dfs2(int v)
{
if(scc[v]) return ;
scc[v]=scc_cnt;
for(int i=0;i<G2[v].size();i++){
if(!scc[G2[v][i]]) _dfs2(G2[v][i]);
}
}
void find_scc()
{
S.clear();
for(int i=1;i<=n;i++) _dfs1(i);
for(int i=n-1;i>=0;i--)
if(!scc[S[i]]){
scc_cnt++;_dfs2(S[i]);
}
}
int main()
{
int T,i,j,u,v,a,b;
while(~scanf("%d%d",&n,&m)){
scc_cnt=0;a=b=0;
memset(vis,0,sizeof(vis));
memset(scc,0,sizeof(scc));
for(i=1;i<=n;i++){
G[i].clear();
G2[i].clear();
ru[i]=chu[i]=1;
}
for(i=0;i<m;i++){
scanf("%d%d",&u,&v);
G[u].push_back(v);
G2[v].push_back(u);
}
find_scc();
for(u=1;u<=n;u++){
int L=G[u].size();
for(j=0;j<L;j++){
v=G[u][j];
if(scc[u]!=scc[v])
chu[scc[u]]=ru[scc[v]]=0;
}
}
for(i=1;i<=scc_cnt;i++){
if(ru[i]) a++;
if(chu[i]) b++;
}
if(b>a) a=b;
if(scc_cnt==1) a=0;
printf("%d
",a);
}
return 0;
}
如图，缩点后可能出现“多对多”的情况，对于每一个入度为0的点（反图中），vis表计避重。
HDU3639#include<iostream> #include<memory.h> #include<algorithm> #include<vector> using namespace std; const int maxn=5010; int scc[maxn],cnt[maxn],ans[maxn],vis[maxn]; int in0[maxn]; vector<vector<int> >G,G2,G3;//动态分配 ，比直接开maxn个省200ms
vector<int> S; int n,m,Max,scc_cnt; void _update() { Max=scc_cnt=0; memset(scc,0,sizeof(scc)); memset(cnt,0,sizeof(cnt)); memset(ans,0,sizeof(ans)); memset(in0,0,sizeof(in0)); memset(vis,0,sizeof(vis)); S.clear(); G.assign(n+1,vector<int>()); G2.assign(n+1,vector<int>()); G3.assign(n+1,vector<int>()); } void dfs1(int v) { if(vis[v]) return ; vis[v]=1; for(int i=0;i<G[v].size();i++) dfs1(G[v][i]); S.push_back(v); } void _dfs2(int v) { if(scc[v]) return ; scc[v]=scc_cnt; for(int i=0;i<G2[v].size();i++) _dfs2(G2[v][i]); } void find_scc() { for(int i=1;i<=n;i++) dfs1(i); for(int i=n-1;i>=0;i--) if(!scc[S[i]]) { scc_cnt++;_dfs2(S[i]); } } int _dfs3(int v) { int tmp=cnt[v]; if(vis[v]) { tmp=0;return tmp; } vis[v]=1; for(int i=0;i<G3[v].size();i++) tmp+=_dfs3(G3[v][i]); return tmp; } int main() { int T,Case=0,i,j,u,v; scanf("%d",&T); while(T--){ scanf("%d%d",&n,&m); _update(); for(i=0;i<m;i++){ scanf("%d%d",&u,&v); u++;v++; G[u].push_back(v); G2[v].push_back(u); } find_scc(); for(i=1;i<=n;i++) { in0[i]=1; cnt[scc[i]]++; } for(u=1;u<=n;u++){ for(j=0;j<G[u].size();j++){ v=G[u][j]; if(scc[u]!=scc[v]){ in0[scc[u]]=0; G3[scc[v]].push_back(scc[u]); } } } for(i=1;i<=n;i++) if(in0[scc[i]]){ memset(vis,0,sizeof(vis)); ans[i]=_dfs3(scc[i]); if(ans[i]>Max) Max=ans[i]; } printf("Case %d: %d ",++Case,Max-1); bool fir=true; for(i=1;i<=n;i++){ if(ans[i]==Max){ if(!fir) printf(" "); else fir=false; printf("%d",i-1); } } printf(" "); } return 0; }
HDU5934
#include <iostream>
#include <vector>
#include <stack>
#include <cstring>
#include <cstdio>
#include <memory.h>
using namespace std;
const int maxn=4010;
long long X,Y,Z;
int vis[maxn],scc[maxn],ru[maxn],scc_cnt,n;
int x[maxn],y[maxn],r[maxn],c[maxn],Min[maxn];
vector<int>G[maxn];
vector<int>G2[maxn];
vector<int>S;
void _dfs1(int v)
{
if(vis[v]) return ;
vis[v]=1;
for(int i=0;i<G[v].size();i++) _dfs1(G[v][i]);
S.push_back(v);
}
void _dfs2(int v)
{
if(scc[v]) return ;
scc[v]=scc_cnt;
for(int i=0;i<G2[v].size();i++){
if(!scc[G2[v][i]])
_dfs2(G2[v][i]);
}
}
void find_scc()
{
S.clear();
for(int i=1;i<=n;i++) _dfs1(i);
for(int i=n-1;i>=0;i--)
if(!scc[S[i]]){
scc_cnt++;
_dfs2(S[i]);
}
}
int main()
{
int T,i,j,u,v,a,b,Case=0,ans;
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
scc_cnt=0;a=0;b=0;ans=0;
memset(vis,0,sizeof(vis));
memset(scc,0,sizeof(scc));
for(i=1;i<=n;i++){
G[i].clear();
G2[i].clear();
ru[i]=1;
}
for(i=1;i<=n;i++)
scanf("%d%d%d%d",&x[i],&y[i],&r[i],&c[i]);
for(i=1;i<=n;i++)
for(j=1;j<=n;j++){
X=x[i]-x[j];Y=y[i]-y[j];Z=r[i];
if(X*X+Y*Y<=Z*Z){
G[i].push_back(j);
G2[j].push_back(i);
}
}
find_scc();
for(u=1;u<=n;u++){
int Len=G[u].size();
for(j=0;j<Len;j++){
v=G[u][j];
if(scc[u]!=scc[v])
ru[scc[v]]=0;
}
}
for(i=1;i<=scc_cnt;i++) Min[i]=10000;
for(i=1;i<=n;i++)
{
if(c[i]<Min[scc[i]])
Min[scc[i]]=c[i];
}
for(i=1;i<=scc_cnt;i++)
if(ru[i]) ans+=Min[i];
printf("Case #%d: %d
",++Case,ans);
}
return 0;
}