很好玩的算法
強(qiáng)連通+縮點(diǎn)可以把一塊點(diǎn)看成一個(gè)點(diǎn)，大大加快算法。還有一些無法解決的問題也可以用這個(gè)來解決
前幾天在林學(xué)院做題的時(shí)候胡搞搞出來了，哈哈
今天又A了一道
最近對圖對樹越來越有感覺了
http://acm.hdu.edu.cn/showproblem.php?pid=2767
#include "stdio.h"
#include "algorithm"
using namespace std;
#define maxn 20001
struct Node {
int to;
Node * next;
}list[maxn],opp[maxn];
struct SCC{
int time;
int newid;
int idx;
}hh[maxn];
int time,newid;
bool flag;
bool hash[maxn];
bool hashid[maxn];
bool gashid[maxn];
//--------------------------------------------
void dfs(int idx) {
Node * buf;
buf = list[idx].next;
while(buf) {
if(!hash[buf->to]) {
hash[buf->to] = true;
dfs(buf->to);
}
buf = buf->next;
}
if(time == 7)
time = 7;
hh[idx].time = time ++;
hh[idx].idx = idx;
}
void dfs2(int idx) {
Node * buf;
buf = opp[idx].next;
while(buf) {
if(!hash[buf->to]) {
hash[buf->to] = true;
dfs2(buf->to);
}
buf = buf->next;
}
hh[idx].newid = newid;
}
void dfs3(int idx) {
Node * buf;
buf = list[idx].next;
while(buf) {
if(hh[idx].newid != hh[buf->to].newid) {
hashid[hh[idx].newid] = true;
gashid[hh[buf->to].newid] = true;
}
if(!hash[buf->to]) {
hash[buf->to] = true;
dfs3(buf->to);
}
buf = buf->next;
}
}
bool cmp(SCC a,SCC b) {
return a.time > b.time;
}
//-----------------------------------------
int main() {
int n,i,a,b,m,T;
Node * buf;
scanf("%d",&T);
while(T--) {
scanf("%d%d",&n,&m);
for(i = 1 ; i <= n ; i ++) {
list[i].next = NULL;
opp[i].next = NULL;
}
while(m --) {
scanf("%d%d",&a,&b);
buf = (Node *)malloc(sizeof(Node)); //正圖
buf->to = b;
buf->next = list[a].next;
list[a].next = buf;
buf = (Node *)malloc(sizeof(Node)); //反圖
buf->to = a;
buf->next = opp[b].next;
opp[b].next = buf;
}
memset(hash,false,sizeof(bool)*(n+1));
time = 0;
for(i = 1 ; i <= n ; i ++) { //先確定時(shí)間戳
if(!hash[i]) {
hash[i] = true;
dfs(i);
}
}
sort(hh+1,hh+1+n,cmp); //按時(shí)間戳排序
memset(hash,false,sizeof(bool)*(n+1));
newid = 0;
for(i = 1 ; i <= n ; i ++) { //把點(diǎn)分成幾塊
if(!hash[hh[i].idx]) {
hash[hh[i].idx] = true;
hh[hh[i].idx].newid = ++newid;
dfs2(hh[i].idx);
}
}
if(newid == 1) {
puts("0");
continue;
}
memset(hash,false,sizeof(bool)*(n+1));
memset(hashid,false,sizeof(bool)*(newid+1));
memset(gashid,false,sizeof(bool)*(newid+1));
for(i =1 ; i <= n ; i ++) { //找出塊的出度入度
if(!hash[i]) {
hash[i] = true;
dfs3(i);
}
}
int cnt = 0;
int cnt1 = 0;
for(i = 1; i <= newid ; i ++) {
if(!hashid[i])
cnt ++;
if(!gashid[i])
cnt1 ++;
}
printf("%d\n",cnt>cnt1?cnt:cnt1);
}
return 0;
}
posted on 2009-05-17 20:36
shǎ崽 閱讀(686)
評論(0) 編輯 收藏 引用