BNU 28903 :Unique Path 双连通分量 + 查找边的数量
一道很简单的题，在一张无向图上，去掉所有的双连通分量，求剩下的树（除去双连通分量之后剩下的必为树和单独的点）里面的边的数量，我试着用dfs搜，也就是Tarjan的方法去做，但是一开始DFS写挫了，边的访问没有写好导致无法找出分量的位置，来回调整了好久。
这里处理好之后后面就简单了，找出所有的树然后边相加就行了（用并查集实现的）
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <list>
#include <map>
using namespace std;
#define N 100005
struct edges
{
int u,v;
int next;
} edge[N * 2];
int head[N];
int dfn[N];
bool used[N];
int low[N];
int n,m;
int shu,pre;
int wei[N];
int ans[N];
long long sum;
void add(int u,int v)
{
edge[shu].u = u;
edge[shu].v = v;
edge[shu].next = head[u];
head[u] = shu;
shu++;
}
void Init()
{
memset(edge,0,sizeof(edge));
memset(used,false,sizeof(used));
memset(head,0,sizeof(head));
memset(dfn,0,sizeof(dfn));
memset(low,0,sizeof(low));
pre = 1;
int u,v;
shu = 0;
for(int i=0; i<m; i++)
{
scanf("%d%d",&u,&v);
{
add(u,v);
add(v,u);
}
}
}
void dfs(int u, int t)
{
dfn[u] = low[u] = pre;
pre++;
for(int i = head[u]; i; i = edge[i].next)
{
int v = edge[i].v;
if(!dfn[v])
{
dfs(v,u);
low[u] = min(low[u] , low[v]);
if(low[v] <= dfn[u])
used[u] = used[v] = true;
continue;
}
if(v != t)
low[u] = min(low[u],dfn[v]);
}
//cout<<u<<' '<<dfn[u]<<' '<<low[u]<<'a'<<endl;
}
int find(int x)
{
if(x == wei[x])
{
return x;
}
int t = find(wei[x]);
wei[x] = t;
return t;
}
int main()
{
int t,cas = 0;
scanf("%d",&t);
while(t--)
{
cas++;
scanf("%d%d",&n,&m);
Init();
for(int i=1; i<=n; i++)
{
if(!used[i])
{
dfs(i,0);
}
}
//cout<<'a'<<endl;
for(int i=1;i<=n;i++)
{
wei[i] = i;
ans[i] = 1;
}
for(int i=1; i<=n; i++)
{
for(int j = head[i];j;j = edge[j].next)
{
int v = edge[j].v;
if(!used[i] && !used[v])
{
int x = find(i);
int y = find(v);
if(x != y)
{
wei[y] = x;
ans[x] += ans[y];
ans[y] = 0;
}
}
}
}
// for(int i=1;i<=shu;i++)
// {
// cout<<ans[i]<<' ';
// }
// cout<<endl;
sum = 0;
memset(used,false,sizeof(used));
for(int i=1;i<=n;i++)
{
int x = find(i);
if(!used[x])
{
used[x] = true;
sum += ans[x] * (ans[x] - 1) / 2;
//cout<<sum<<' '<<ans[x]<<' '<<x<<endl;
}
}
printf("Case #%d: %lld\n",cas,sum);
}
return 0;
}
HDU4635 ： Strongly connected 强连通分量+出入度判断
既然做了双连通，自然想到了去把强连通也写一下（本质上双连通的写法是按强连通来的）
这道题是求在已知的有向图上最多能加多少条边（不能使已有的图整体强连通）如果本身给的就是强连通图，输出-1。
这道题我们需要的就是把所有的强连通分量都求出来（包括点），然后找出其中能添加的边个数。
因为出入度都为1的点在这里我们不能把其当做是一个独立的强连通分量，所以需要判断出入度。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <list>
#include <map>
using namespace std;
#define N 100005
struct Edges
{
int u,v;
int next;
} edge[N*2];
int head[N];
int dfn[N];
int low[N];
int fan[N];
bool used[N];
bool use[N];
int n,m,shu,front;
vector<int> Vector;
int num,pre;
int ans[N];
bool in[N];
bool out[N];
void add(int u,int v)
{
edge[shu].u = u;
edge[shu].v = v;
edge[shu].next = head[u];
head[u] = shu;
shu++;
}
void Init()
{
memset(edge,0,sizeof(edge));
memset(head,0,sizeof(head));
memset(dfn,0,sizeof(dfn));
memset(low,0,sizeof(low));
memset(used,false,sizeof(used));
memset(use,false,sizeof(use));
memset(fan,0,sizeof(fan));
int u,v;
num = pre = 0;
shu = 1;
for(int i=0; i<m; i++)
{
scanf("%d%d",&u,&v);
add(u,v);
}
}
void dfs(int u)
{
//cout<<u<<' '<<edge[head[u]].v<<'b'<<endl;
front++;
pre++;
Vector.push_back(u);
dfn[u] = low[u] = pre;
used[u] = use[u] = true;
for(int i = head[u]; i; i = edge[i].next)
{
int v = edge[i].v;
//cout<<v<<'c'<<endl;
if(used[v])
{
if(use[v]) low[u] = min(low[u],dfn[v]); //必须加入这个来判重和去重，不然分量的计算会出现偏差
continue;
}
dfs(v);
low[u] = min(low[u],low[v]);
}
if(low[u] == dfn[u])
{
//cout<<u<<endl;
num++;
int mark = Vector.back();
Vector.pop_back();
fan[mark] = num;
use[mark] = false;
while(mark != u)
{
mark = Vector.back();
Vector.pop_back();
fan[mark] = num;
use[mark] = false;
}
}
}
int main()
{
int t,cas = 0;
scanf("%d",&t);
while(t--)
{
cas++;
scanf("%d%d",&n,&m);
Init();
for(int i=1; i<=n; i++)
{
//cout<<i<<' '<<used[i]<<endl;
if(!used[i])
{
front = -1;
Vector.clear();
dfs(i);
}
}
//cout<<num<<endl;
if(num == 1)
{
printf("Case %d: -1\n",cas);
continue;
}
memset(ans,0,sizeof(ans));
memset(in,false,sizeof(in));
memset(out,false,sizeof(out));
for(int i=1;i<=n;i++)
{
ans[fan[i]]++;
}
for(int i=1;i<shu;i++)
{
int x = fan[edge[i].u];
int y = fan[edge[i].v];
if(x != y)
{
in[y] = true;
out[x] = true;
}
}
int sum = N;
for(int i=1;i <= num;i++)
{
if(!in[i] || !out[i])sum = min(sum,ans[i]);
}
//cout<<sum<<endl;
sum = n * (n - 1) - sum * (n - sum) - m;
printf("Case %d: %d\n",cas,sum);
}
return 0;
}