#38372: 我cpe官網和uDebug網站的側資都過，但是UVA和這裡的網站過不了，看不到測資不知道甚麼原因，求解
#include <iostream> //可用1和-1代表相反(色)
#include<unordered_map>
#include<vector>
using namespace std;
int main(){
int n;
while(cin>>n&&n){
int l;
cin>>l;
unordered_map<int,vector<int>> unmap;
string s="BICOLORABLE.";
int visit[n],color[n];
for(int i=0;i<n;i++){
visit[i]=0;
color[i]=1;
if(!unmap[i].empty()){
unmap[i].clear();
}
}
for(int i=0;i<l;i++){
int a,b;
cin>>a>>b;
unmap[a].push_back(b);
unmap[b].push_back(a);
}
for(int i=0;i<n;i++){
if(visit[i]==0){
visit[i]=1;
while(!unmap[i].empty()){
color[unmap[i].back()]= - color[i];
visit[unmap[i].back()]=1;//cout<<unmap[i].back()<<endl;
unmap[i].pop_back();
// cout<<unmap[i].back()<<endl;
}
}else{
while(!unmap[i].empty()){
if(color[i]==color[unmap[i].back()]){
s="NOT BICOLORABLE.";
break;
}unmap[i].pop_back();
// unmap[i].erase(unmap[i].end()); //會錯，要用vec.pop_back();
}
}
if(s=="NOT BICOLORABLE.") break;
}
cout<<s<<endl;
}
return 0;
}
#38373: Re: 我cpe官網和uDebug網站的側資都過，但是UVA和這裡的網站過不了，看不到測資不知道甚麼原因，求解
liaoweichen1024@gmail.com
(M_SQRT)
學校
:
新北市立新莊高級中學
編號 : 195452
來源 : [150.117.3.92]
最後登入時間 ：
2024-11-21 20:54:31
4
3
0 2
2 3
3 1
0
#38376: Re: 我cpe官網和uDebug網站的側資都過，但是UVA和這裡的網站過不了，看不到測資不知道甚麼原因，求解
liaoweichen1024@gmail.com
(M_SQRT)
學校
:
新北市立新莊高級中學
編號 : 195452
來源 : [150.117.3.92]
最後登入時間 ：
2024-11-21 20:54:31
這題的標準解法應該是bfs或dfs (剛剛試了一下都是10ms)
如果要拿你這支程式改，而不使用bfs, dfs，那你還得搭配併查集才能解決 (也是10ms)
#38429: Re: 我cpe官網和uDebug網站的側資都過，但是UVA和這裡的網站過不了，看不到測資不知道甚麼原因，求解
這題的標準解法應該是bfs或dfs (剛剛試了一下都是10ms)
如果要拿你這支程式改，而不使用bfs, dfs，那你還得搭配併查集才能解決 (也是10ms)
哦哦，謝謝，我也有發現錯了，應該要從拜訪到的節點繼續拜訪 ( 我用BFS(queue) )。但是用二維vector第二次n輸入0會錯，改用unordered_map就不會錯，不知道是為甚麼...
#include <iostream>
#include<queue>
#include<vector>
#include<unordered_map>
#include<string>
using namespace std;
string s;
unordered_map<int,vector<int> > v;
//vector<vector<int> > v(200,vector<int> (200));
queue<int> q;
void DFS(){
q.push(0);
int paint[200]={0};
paint[0]=1;
while(!q.empty()){
int i=q.front();
q.pop();
while(!v[i].empty()){
if(paint[v[i].back()]==0){
paint[v[i].back()]= - paint[i];
q.push(v[i].back());
v[i].pop_back();
}else{
if(paint[i]==paint[v[i].back()]){
s="NOT BICOLORABLE.";
return;
}v[i].pop_back();
}
}
}
}
int main(){
int n;
while(cin>>n&&n){
int L;
cin>>L;
int j=0;
while(!v[j].empty()){
v[j].clear();
j++;
}while(!q.empty()) q.pop();
// for(int i=0;i<200;i++) paint[i]=0;
int l,r;
while(L--){
cin>>l>>r;
v[l].push_back(r);
v[r].push_back(l);
}
s="BICOLORABLE.";
DFS();
cout<<s<<endl;
}
return 0;
}
ZeroJudge Forum