Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- #define FOR(i,a,b) for(int i = (a); i <= (b); ++i)
- #define FORD(i,a,b) for(int i = (a); i >= (b); --i)
- #define mini(a,b) a=min(a,b)
- #define maxi(a,b) a=max(a,b)
- //#define sz(a) (int) a.size()
- #define mp make_pair
- #define pb push_back
- #define st first
- #define nd second
- typedef vector<int> vi;
- typedef long long ll;
- typedef long double ld;
- typedef pair<int, int> pii;
- const int N = 1e6+2;
- int n,m;
- vector<int> V[N],R[N];
- // topsort;
- stack<int> s;
- bitset<N> o,o2;
- int war[N];
- int kl;
- void addEdge(int a, int b) {
- V[a].pb(b);
- R[b].pb(a);
- }
- void wczytaj() {
- ios_base::sync_with_stdio(0);
- cin.tie(0);
- int a,b;
- cin>>n>>m;
- FOR(i,1,m) {
- cin>>a>>b;
- addEdge(a,b);
- }
- }
- void dfs(int p) {
- o[p]=1;
- for(int i=0; i<V[p].size(); ++i)
- if(!o[V[p][i]]) dfs(V[p][i]);
- s.push(p);
- }
- void puscdfsy() {
- FOR(i,1,n) {
- if(!o[i]) dfs(i);
- }
- }
- void revdfs(int p) {
- o2[p]=1;
- war[s.top()]=kl;
- s.pop();
- for(int i=0; i<R[p].size(); ++i)
- if(!o2[R[p][i]]) revdfs(R[p][i]);
- }
- void skladowe() {
- int w;
- while(!s.empty()) {
- w=s.top();
- ++kl;
- revdfs(w);
- }
- }
- void odpowiedz() {
- int q,a,b;
- cin>>q;
- FOR(i,1,q) {
- cin>>a>>b;
- if(war[a]==war[b]) cout<<"MISJA UDANA\n";
- else cout<<"MISJA NIEUDANA\n";
- }
- }
- signed main() {
- wczytaj();
- puscdfsy();
- skladowe();
- odpowiedz();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement