It would be great if someone could tell me where the following approach fails …
For each node after creating the list of the nodes to which it can be connected,
I made a multisource bfs type approach with the pushed nodes being the ones with outdegree zero.
while processing a popped node …what i did is removed the popped node from the list of all nodes and after removing it, if a list gets emptied i inserted it in the queue and hence continued the bfs.
i got a wrong answer verdict. Ya!! its a very common question of max flow max. bipartite but i wanted to know whats wrong with the above approach!!! I could not find any counter case to this! i feel each time it should give a optimal solution with minimum number of nodes with indegree zero!!
I would be grateful enough if someone finds me my mistake.
That worked for me if I’m understanding you correctly.
https://www.codechef.com/viewsolution/30233496
#include <bits/stdc++.h>
using namespace std;
#define fl(i,a,b) for(int i=a; i<b; i++)
#define bfl(i,a,b) for(int i=a-1; i>=b; i–)
#define Shazam ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define ll long long
#define pb push_back
#define ff first
#define ss second
#define all© c.begin(),c.end()
#define endl “\n”
#define de(x) cout << #x << " " << x << endl;
#define deb(x,y) cout << x << ’ ’ << y << endl;
#define get(a,n) fl(i,0,n) cin>>a[i];
#define pr(a,n) fl(i,0,n) cout<<a[i]<<" "; cout<<endl;
#define test() int tt; cin>>tt; while(tt–)
int main() {
Shazam;
test() {
int n, k;
cin >> n >> k;
int a[k][n], pos[k][n];
fl(i, 0, k) fl(j, 0, n) {
int x;
cin >> x;
a[i][j] = x-1;
pos[i][x-1] = j;
}
set<int> s[n];
fl(i, 0, n) fl(j, 0, n) if(i != j) {
bool f = true;
fl(l, 0, k) {
if(pos[l][i] > pos[l][j]) {
f = false;
break;
}
}
if(f) {
s[i].insert(j);
}
}
queue<int> q;
fl(i, 0, n) {
if(s[i].empty()) {
q.push(i);
}
}
vector<int> ans(n, 0);
bool in[n] = {false};
while(not q.empty()) {
int u = q.front();
q.pop();
fl(i, 0, n) {
if(s[i].find(u) != s[i].end()) {
s[i].erase(u);
if(s[i].empty()) {
ans[i] = u+1;
in[u] = true;
q.push(i);
}
}
}
}
cout << n - accumulate(in, in + n, 0) << endl;
fl(i, 0, n) {
cout << ans[i] << " " ;
}
cout << endl;
}
}
Can u plz find where i went wrong! How mine was diff from urs
At least use ` ``
Can you explain what was the idea behind this approach. I kind of not getting the approach.
It’s a self correcting greedy algorithm. Using the sequences, find the allowed edges.
Then iterate over all nodes. see if you can place the node somewhere. It is okay to displace other edges also, until some other edge finds a free space. That means the edge can go there and update the edges.
for example
n=4
1 can go to 3 and 4
2 can go to 3
node 1:
we put it at 3
node 2:
we check 3.
1 is going to 3.
can we move 1 to something else?
yes?
we move it and put 2 at 3
no? we move on to the next node
The chain may be arbitrarily large.
I have also approached the problem in a similar way. Just a little bit of difference.Couldn’t find where it is getting wrong.
https://www.codechef.com/viewsolution/30535209
You are trying to find maximum matching in Bipartite graph?
Oh, that’s what I did. I didn’t really think in flows or bipartite graph though.
while(k--) {
for(int i=0; i<n; ++i) {
cin >> a[i], --a[i];
//remove edges
for(int j=0; j<i; ++j)
adj[a[j]][a[i]]=0;
}
}
https://www.codechef.com/viewsolution/30509361
consider
4 1
1 2 3 4
here why are we removing edges (1 3), (2 3), (1 4) ,(2 4) ,(3 4) what actually we are trying to do by removing this edge ?? please help!!!
Because those edges are not allowed as specified by the question.
Each of the given permutations is a valid topological sort of the graph. Formally, for each valid kk and each i,ji,j (1≤i<j≤N1≤i<j≤N), there is no edge from the node Ak,jAk,j to the node Ak,iAk,i.
4 1
1 2 3 4
(2 1) (4 1) (3 1) (3 2) (4 3) this edges are not allowed.
But this edges (1 3), (2 3), (1 4) ,(2 4) ,(3 4) are allowed.
He’s used the edges backward. Nothing more.
ok thanks !! He just did opposite but the answer remains the same
Check this testcase
9 2
8 5 7 9 4 3 2 6 1
5 8 3 7 6 1 9 4 2
your solution is giving 3 but the answer should be 2