HDU 1269.迷宫城堡

351

题目



Description  


为了训练小希的方向感,Gardon建立了一座大城堡,里面有N个房间(N<=10000)和M条通道(M<=100000),每个通道都是单向的,就是说若称某通道连通了A房间和B房间,只说明可以通过这个通道由A房间到达B房间,但并不说明通过它可以由B房间到达A房间。Gardon需要请你写个程序确认一下是否任意两个房间都是相互连通的,即:对于任意的i和j,至少存在一条路径可以从房间i到房间j,也存在一条路径可以从房间j到房间i。




Input  


输入包含多组数据,输入的第一行有两个数:N和M,接下来的M行每行有两个数a和b,表示了一条通道可以从A房间来到B房间。文件最后以两个0结束。



Output  


对于输入的每组数据,如果任意两个房间都是相互连接的,输出"Yes",否则输出"No"。



Sample Input  


3 3
1 2
2 3
3 1
3 3
1 2
2 3
3 2
0 0



Sample Output  


Yes
No



题解


强连通分量模板题
用来测试自己写的模板
具体思路看 **强连通分量**

代码


/*
By:OhYee
Github:OhYee
Blog:http://www.oyohyee.com/
Email:oyohyee@oyohyee.com

かしこいかわいい?
エリーチカ!
要写出来Хорошо的代码哦~
*/
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <set>
#include <list>
#include <queue>
#include <stack>
#include <string>
#include <vector>
#include <bitset>
#include <functional>

using namespace std;

const int INF = 0x7FFFFFFF;
const double eps = 1e-10;

const int maxn = 10005;

//Kosaraju
const int maxm = 100005;

struct Edge {
int u,v;
Edge():u(0),v(0) {}
Edge(int a,int b):u(a),v(b) {}
};
int pos;
Edge edge[maxm];
list<int> L[maxn];
list<int> L2[maxn];

stack<int> s;
bool vis[maxn];
vector<int> SCC[maxn];//得到的强连通分量链表

inline void add(int u,int v) {
edge[pos] = Edge(u,v);
L[u].push_back(pos);
L2[v].push_back(pos);//逆图

pos++;
}

void DFS1(int t) {
if(!vis[t]) {
vis[t] = true;
for(list<int>::iterator i = L[t].begin();i != L[t].end();i++)
DFS1(edge[*i].v);
s.push(t);
}
return;
}

void DFS2(int p,int t) {
if(vis[t]) {
vis[t] = false;
SCC[p].push_back(t);
for(list<int>::iterator i = L2[t].begin();i != L2[t].end();i++)
DFS2(p,edge[*i].u);
}
return;
}

int Kosaraju(int n) {
//第一次DFS
for(int i = 0;i < n;i++)
DFS1(i);

//第二次DFS
int p = 0;
while(!s.empty()) {
int t = s.top();
s.pop();
list< list<int> >::iterator it;
if(vis[t])
DFS2(p++,t);
}
return p;
}


int main() {
cin.tie(0);
cin.sync_with_stdio(false);

int n,m;
while(cin >> n >> m,!(n == 0 && m == 0)) {
for(int i = 0;i < n;i++) {
L[i].clear();
L2[i].clear();
SCC[i].clear();
vis[i] = false;
}
while(!s.empty())s.pop();
pos = 0;

for(int i = 0;i < m;i++) {
int a,b;
cin >> a >> b;
add(a - 1,b - 1);
}

cout << (Kosaraju(n) == 1 ? "Yes" : "No") << endl;


}
return 0;
}



/*
By:OhYee
Github:OhYee
Blog:http://www.oyohyee.com/
Email:oyohyee@oyohyee.com

かしこいかわいい?
エリーチカ!
要写出来Хорошо的代码哦~
*/
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <set>
#include <list>
#include <queue>
#include <stack>
#include <string>
#include <vector>
#include <bitset>
#include <functional>

using namespace std;

const int INF = 0x7FFFFFFF;
const double eps = 1e-10;

const int maxn = 10005;

//Tarjan
const int maxm = 100005;

struct Edge {
int u,v;
Edge():u(0),v(0) {}
Edge(int a,int b):u(a),v(b) {}
};
int pos;
Edge edge[maxm];
list<int> L[maxn];

stack<int> s;
bool inStack[maxn];
vector<int> SCC[maxn];//得到的强连通分量链表
int cnt,Index;
int DFN[maxn],Low[maxn];

inline void add(int u,int v) {
edge[pos] = Edge(u,v);
L[u].push_back(pos);
pos++;
}

void tarjan(int u) {
if(DFN[u] != -1)
return;

DFN[u] = Low[u] = ++Index;
s.push(u);
inStack[u] = true;

for(list<int>::iterator it = L[u].begin();it != L[u].end();it++) {
int v = edge[*it].v;

if(DFN[v] == -1) {
tarjan(v);
Low[u] = min(Low[u],Low[v]);
} else if(inStack[v]) {
Low[u] = min(Low[u],DFN[v]);
}

}
if(DFN[u] == Low[u]) {
int v = s.top();
s.pop();
inStack[v] = false;

SCC[cnt++].push_back(v);

while(u != v) {
v = s.top();
s.pop();
inStack[v] = false;

SCC[cnt - 1].push_back(v);
}
}
}

int Tarjan(int n) {
cnt = 0;
Index = 0;
while(!s.empty())s.pop();
memset(inStack,false,sizeof(inStack));
memset(DFN,-1,sizeof(DFN));
memset(Low,-1,sizeof(Low));

for(int i = 0;i < n;i++)
tarjan(i);
return cnt;

}

int main() {
cin.tie(0);
cin.sync_with_stdio(false);

int n,m;
while(cin >> n >> m,!(n == 0 && m == 0)) {
for(int i = 0;i < n;i++) {
L[i].clear();
SCC[i].clear();
}
while(!s.empty())s.pop();
pos = 0;

for(int i = 0;i < m;i++) {
int a,b;
cin >> a >> b;
add(a - 1,b - 1);
}

cout << (Tarjan(n) == 1 ? "Yes" : "No") << endl;


}
return 0;
}
发布评论
  • 点击查看/关闭被识别为广告的评论