## 1242 - Necklace

All about problems in Volume 12. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### 1242 - Necklace

Use this thread to discuss this problem.
Check input and AC output for thousands of problems on uDebug!

jddantes
Learning poster
Posts: 73
Joined: Sat Mar 08, 2014 8:55 am

### Re: 1242 - Necklace

Does doing BFS twice (making sure to not use an edge twice) work?
My code matches Morass' output on uDebug.

Code: Select all

``````#include <bits/stdc++.h>

using namespace std;

typedef pair<int,int> pi;
typedef tuple<int,int,int> t3;

bool edge_used[100000+10];

int N,M;
int S,T;

bool vis[10000+10];
pi pred[10000+10];
bool augment(){
bool found = false;

queue<t3> que; // node, pre, edge
que.push(t3(S,-1, -1));
memset(vis, 0, sizeof vis);

while(!que.empty()){
t3 t = que.front();
que.pop();

int node = get<0>(t);
int pre = get<1>(t);
int edge = get<2>(t);

if(vis[node]) continue;
pred[node] = pi(pre, edge);
vis[node] = true;

if(node == T){
found = true;
break;
}

for(auto p : adjList[node]){
int adj = p.first;
int eid = p.second;

if(edge_used[eid]) continue;

}
}

if(found){
int cur = T;
while(1){
int pre = pred[cur].first;
int eid  =pred[cur].second;

edge_used[eid] = true;

if(pre == S) break;
cur = pre;
}
}

return found;
}

int main(){
int cn = 0;
while(scanf("%d %d",&N, &M)!=EOF){
if(!N && !M) break;
cn++;

for(int x = 0; x<M; x++){
int u,v;
scanf("%d %d", &u, &v);
u--;
v--;
}
scanf("%d %d", &S, &T);
S--;
T--;
memset(edge_used, 0, sizeof edge_used);

int ctr = 0;
while(1){
bool r = augment();
if(!r) break;
if(r){
ctr++;
if(ctr == 2){
break;
}
}
}

printf("Case %d: %s\n", cn, ctr == 2 ? "YES": "NO");
}

return 0;
}
``````

jddantes
Learning poster
Posts: 73
Joined: Sat Mar 08, 2014 8:55 am

### Re: 1242 - Necklace

Nevermind, I now know why that scheme will fail.