Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <algorithm>
- #include <stack>
- using namespace std;
- int n;
- int m;
- bool odw[1000000+5];
- int SSS[1000000+5];
- int krawedzie[1000000+5][2];
- int sorted_SSS[1000000+5];
- int co_na_pozycji_sorted[1000000+5];
- int max_SSS_na_sciezce[1000000+5];
- int ile_opcji_dojscia[1000000+5];
- bool czy_jest_petla[1000000+5];
- vector <int> sas[1000000+5];
- vector <int> sas_rev[1000000+5];
- vector <int> sas_SSS_rev[1000000+5];
- vector <int> zawartosc_SSS[1000000+5];
- stack <int> S;
- void DFS_make_stack(int i)
- {
- odw[i] = 1;
- for(int j=0; j<sas[i].size(); j++)
- if(!odw[sas[i][j]])
- DFS_make_stack(sas[i][j]);
- S.push(i);
- }
- void DFS_make_SSS(int w, int nr_SSS)
- {
- odw[w] = 1;
- //cout<<"w: "<<w<<" nr_SSS: "<<nr_SSS<<endl;
- SSS[w] = nr_SSS;
- zawartosc_SSS[nr_SSS].push_back(w);
- for(int i=0; i<sas_rev[w].size(); i++)
- if(!odw[sas_rev[w][i]])
- DFS_make_SSS(sas_rev[w][i], nr_SSS);
- }
- int nr = 1;
- void DFS_topo(int w)
- {
- odw[w] = 1;
- for(int i=0; i<sas_SSS_rev[w].size(); i++)
- if(!odw[sas_SSS_rev[w][i]])
- DFS_topo(sas_SSS_rev[w][i]);
- sorted_SSS[w] = nr;
- co_na_pozycji_sorted[nr] = w;
- nr++;
- }
- int main()
- {
- cin>>n;
- cin>>m;
- int t1;
- int t2;
- for(int i=1; i<=m; i++)
- {
- cin>>t1;
- cin>>t2;
- krawedzie[i][0] = t1;
- krawedzie[i][1] = t2;
- if(t1==t2)
- czy_jest_petla[t1] = 1;
- sas[t1].push_back(t2);
- sas_rev[t2].push_back(t1);
- }
- for(int i=1; i<=(n+1); i++)
- if(!odw[i])
- DFS_make_stack(i);
- for(int i=1; i<=(n+1); i++)
- odw[i] = 0;
- ///ODWRACAM KRAWEDZIE -> KORZYSTAM Z SAS_REV
- int top;
- while(!S.empty())
- {
- top = S.top();
- //cout<<"top: "<<top<<endl;
- if(!odw[top])
- DFS_make_SSS(top, top);
- S.pop();
- }
- for(int i=1; i<=(n+1); i++)
- odw[i] = 0;
- // for(int i=1; i<=(n+1); i++)
- // cout<<"i: "<<i<<" SSS: "<<SSS[i]<<" roz: "<<roz_SSS[i]<<endl;
- for(int i=1; i<=m; i++)
- {
- int od_ = SSS[krawedzie[i][0]];
- int do_ = SSS[krawedzie[i][1]];
- if(od_ != do_)
- {
- sas_SSS_rev[do_].push_back(od_);
- }
- }
- DFS_topo(n+1);
- vector<int> zawsze;
- //cout<<"sas_SSS_rev[4][0]: "<<sas_SSS_rev[4][0]<<endl;
- // for(int i=1; i<=4; i++)
- // cout<<"i: "<<i<<" co: "<<co_na_pozycji_sorted[i]<<endl;
- for(int i=sorted_SSS[n+1]; i>=1; i--)
- {
- int SSS_ = co_na_pozycji_sorted[i];
- // cout<<"SSS_: "<<SSS_<<endl;
- if(SSS_ == (n+1) || max_SSS_na_sciezce[SSS_] != 0)
- {
- max_SSS_na_sciezce[SSS_] = max(max_SSS_na_sciezce[SSS_], int(zawartosc_SSS[SSS_].size()));
- if(czy_jest_petla[SSS_])
- max_SSS_na_sciezce[SSS_]++;
- if(max_SSS_na_sciezce[SSS_] > 1)
- zawsze.push_back(SSS_);
- for(int j=0; j<sas_SSS_rev[SSS_].size(); j++)
- {//cout<<"sas: "<<sas_SSS_rev[SSS_][j]<<endl;
- max_SSS_na_sciezce[sas_SSS_rev[SSS_][j]] = max(max_SSS_na_sciezce[sas_SSS_rev[SSS_][j]], max_SSS_na_sciezce[SSS_]);}
- }
- }
- // cout<<zawsze.size()<<endl;
- // for(int i=0; i<zawsze.size(); i++)
- // cout<<zawsze[i]<<endl;
- ile_opcji_dojscia[n+1] = 1; ///
- for(int i=sorted_SSS[n+1]; i>=1; i--)
- {
- int SSS_ = co_na_pozycji_sorted[i];
- // cout<<"SSS_: "<<SSS_<<endl;
- for(int j=0; j<sas_SSS_rev[SSS_].size(); j++)
- {//cout<<"sas: "<<sas_SSS_rev[SSS_][j]<<endl;
- ile_opcji_dojscia[sas_SSS_rev[SSS_][j]] += ile_opcji_dojscia[SSS_];}
- if(ile_opcji_dojscia[SSS_] > 36500)
- zawsze.push_back(SSS_);
- }
- vector<int>zawsze_w;
- for(int i=0; i<zawsze.size(); i++)
- {
- int SSS_ = zawsze[i];
- for(int j=0; j<zawartosc_SSS[SSS_].size(); j++)
- {
- zawsze_w.push_back(zawartosc_SSS[SSS_][j]);
- }
- }
- if(zawsze_w.size() > 0)
- {
- cout<<"zawsze"<<endl;
- cout<<zawsze_w.size()<<endl;
- sort(zawsze_w.begin(), zawsze_w.end());
- for(int i=0; i<zawsze_w.size(); i++)
- cout<<zawsze_w[i]<<' ';
- }
- else
- {
- int max_ = 0;
- for(int i=1; i<=n; i++)
- max_ = max(max_, ile_opcji_dojscia[i]);
- int ile = 0;
- for(int i=1; i<=n; i++)
- if(ile_opcji_dojscia[i] == max_)
- ile++;
- cout<<max_<<endl;
- cout<<ile<<endl;
- for(int i=1; i<=n; i++)
- if(ile_opcji_dojscia[i] == max_)
- cout<<i<<' ';
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement