Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- using namespace std;
- vector<int>sasiedzi[200+5];
- vector<int>sasiedzi_gornych[200+5];
- bool jest_dolny[200+5];
- bool odw[200+5];
- int odw_nr[200+5];
- int partner[200+5];
- int n;
- int nr = 1;
- int wynik = 0;
- void DFS_odw(int w)
- {
- odw[w] = true;
- for(int i=0; i<sasiedzi[w].size(); i++)
- if(odw[sasiedzi[w][i]] == false)
- DFS_odw(sasiedzi[w][i]);
- }
- bool Match(int w)
- {
- // cout<<endl;
- // cout<<"WYWOLANO MATCH DLA W: "<<w<<endl;
- odw_nr[w] = nr;
- ///DLA KAZDEJ WOLNEJ
- int ile_opcji = sasiedzi_gornych[w].size();
- for(int i=0; i<ile_opcji; i++)
- {
- int akt_opcja = sasiedzi_gornych[w][i];
- // cout<<"AKT OPCJA: "<<akt_opcja<<endl;
- if(partner[akt_opcja] == 0)
- {
- partner[akt_opcja] = w;
- // cout<<"wolna, teraz "<<akt_opcja<<"ma partnera: "<<w<<endl;
- return 1;
- }
- }
- for(int i=0; i<ile_opcji; i++)
- {
- int akt_opcja = sasiedzi_gornych[w][i];
- int part_opcji = partner[akt_opcja];
- if(odw_nr[part_opcji] != nr && Match(part_opcji) == 1)
- {partner[akt_opcja] = w; return 1;}
- }
- return 0;
- }
- int main()
- {
- cin>>n;
- int t1;
- int t2;
- for(int i=1; i<n; i++)
- {
- cin>>t1;
- for(int j=1; j<=t1; j++)
- {
- cin>>t2;
- sasiedzi[i].push_back(t2);
- if(t2 == n)
- jest_dolny[i] = true;
- }
- }
- bool istnieje_polaczenie_1_do_n = false;
- for(int i=0; i<sasiedzi[1].size(); i++)
- if(sasiedzi[1][i] == n)
- {istnieje_polaczenie_1_do_n = true; sasiedzi[1].erase(sasiedzi[1].begin() + i); break;}
- /* cout<<"SASIEDZI"<<endl;
- for(int i=1; i<=n; i++)
- {
- cout<<i<<": "<<sasiedzi[i].size()<<endl;
- for(int j=0; j<sasiedzi[i].size(); j++)
- cout<<sasiedzi[i][j]<<" ";
- cout<<endl;
- }*/
- ///DLA KAZDEGO GORENEGO
- for(int i=0; i<sasiedzi[1].size(); i++)
- {
- // cout<<"DLA GORNEGO: "<<sasiedzi[1][i]<<endl;
- for(int j=0; j<=n; j++)
- odw[j] = false;
- DFS_odw(sasiedzi[1][i]);
- for(int j=1; j<=n; j++)
- {
- //cout<<"j: "<<j<<" odw[j]: "<<odw[j]<<" jest_dolny[j]: "<<jest_dolny[j]<<endl;
- if(odw[j] == 1 && jest_dolny[j] == 1)
- {
- // cout<<"dodaje dla: "<<sasiedzi[1][i]<<" wartosc: "<<j<<endl;
- sasiedzi_gornych[sasiedzi[1][i]].push_back(j);
- }
- }
- // cout<<endl;
- }
- /*for(int i=1; i<=n; i++)
- {
- cout<<i<<": "<<sasiedzi_gornych[i].size()<<endl;
- for(int j=0; j<sasiedzi_gornych[i].size(); j++)
- cout<<sasiedzi_gornych[i][j]<<" ";
- cout<<endl;
- }*/
- ///DOTAD OK
- for(int i=0; i<sasiedzi[1].size(); i++)
- {
- wynik += int(Match(sasiedzi[1][i]));
- nr++;
- }
- cout<<wynik+int(istnieje_polaczenie_1_do_n);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement