fork(24) download
copy 
  1. #include<iostream>
  2. #include<stack>
  3. #include<utility>
  4. #include<vector>
  5. #include<algorithm>
  6. #include<cassert>
  7. #include<cstdio>
  8. #define debug(i) cout<<"Reached "<<i<<endl
  9. using namespace std;
  10. using std::string;
  11.  
  12. static struct IO {
  13.         char tmp[1 << 10];
  14.  
  15.         // fast input routines
  16.         char cur;
  17.  
  18. //#define nextChar() (cur = getc_unlocked(stdin))
  19. //#define peekChar() (cur)
  20.         inline char nextChar() { return cur = getc_unlocked(stdin); }
  21.         inline char peekChar() { return cur; }
  22.  
  23.         inline operator bool() { return peekChar(); }
  24.         inline static bool isBlank(char c) { return (c < '-' && c); }
  25.         inline bool skipBlanks() { while (isBlank(nextChar())); return peekChar() != 0; }
  26.  
  27.         inline IO& operator >> (char & c) { c = nextChar(); return *this; }
  28.  
  29.         inline IO& operator >> (char * buf) {
  30.                 if (skipBlanks()) {
  31.                         if (peekChar()) {
  32.                                 *(buf++) = peekChar();
  33.                                 while (!isBlank(nextChar())) *(buf++) = peekChar();
  34.                         } *(buf++) = 0; } return *this; }
  35.  
  36.         inline IO& operator >> (string & s) {
  37.                 if (skipBlanks()) {     s.clear(); s += peekChar();
  38.                         while (!isBlank(nextChar())) s += peekChar(); }
  39.                 return *this; }
  40.  
  41.         inline IO& operator >> (double & d) { if ((*this) >> tmp) sscanf(tmp, "%lf", &d); return *this; }
  42.  
  43. #define defineInFor(intType) \
  44.         inline IO& operator >>(intType & n) { \
  45.                 if (skipBlanks()) { \
  46.                         int sign = +1; \
  47.                         if (peekChar() == '-') { \
  48.                                 sign = -1; \
  49.                                 n = nextChar() - '0'; \
  50.                         } else \
  51.                                 n = peekChar() - '0'; \
  52.                         while (!isBlank(nextChar())) { \
  53.                                 n += n + (n << 3) + peekChar() - 48; \
  54.                         } \
  55.                         n *= sign; \
  56.                 } \
  57.                 return *this; \
  58.         }
  59.  
  60. defineInFor(int)
  61. defineInFor(unsigned int)
  62. defineInFor(long long)
  63.  
  64.         // fast output routines
  65.  
  66. //#define putChar(c) putc_unlocked((c), stdout)
  67.         inline void putChar(char c) { putc_unlocked(c, stdout); }
  68.         inline IO& operator << (char c) { putChar(c); return *this; }
  69.         inline IO& operator << (const char * s) { while (*s) putChar(*s++); return *this; }
  70.  
  71.         inline IO& operator << (const string & s) { for (int i = 0; i < (int)s.size(); ++i) putChar(s[i]); return *this; }
  72.  
  73.         char * toString(double d) { sprintf(tmp, "%lf%c", d, '\0'); return tmp; }
  74.         inline IO& operator << (double d) { return (*this) << toString(d); }
  75.  
  76.  
  77. #define defineOutFor(intType) \
  78.         inline char * toString(intType n) { \
  79.                 char * p = (tmp + 30); \
  80.                 if (n) { \
  81.                         bool isNeg = 0; \
  82.                         if (n < 0) isNeg = 1, n = -n; \
  83.                         while (n) \
  84.                                 *--p = (n % 10) + '0', n /= 10; \
  85.                         if (isNeg) *--p = '-'; \
  86.                 } else *--p = '0'; \
  87.                 return p; \
  88.         } \
  89.         inline IO& operator << (intType n) { return (*this) << toString(n); }
  90.  
  91. defineOutFor(int)
  92. defineOutFor(long long)
  93.  
  94. #define endl ('\n')
  95. #define cout __io__
  96. #define cin __io__
  97. } __io__;
  98.  
  99. vector<vector<int> > v(10005);
  100. vector<bool> disc(10005),exp(10005);
  101. vector<int> t(10005);
  102. stack<int> st,s;
  103. int ret=0;
  104. void visit(int n)
  105. {
  106.     if(disc[n]==true&&exp[n]==false)
  107. 		ret=1;
  108. 	if(disc[n]==false)
  109. 	{
  110. 		disc[n]=true;
  111. 		for(vector<int>::const_iterator it=v[n].begin();it!=v[n].end();it++)
  112. 			visit(*it);
  113. 		exp[n]=true;
  114. 		st.push(n);
  115. 	}
  116. }
  117. int main()
  118. {
  119. 	int n,m;
  120. 	cin>>n>>m;
  121. 	vector<bool> inc(n,false);
  122. 	vector<int> red;
  123. 	while(m--)
  124. 	{
  125. 		int s,d;
  126. 		cin>>s>>d;
  127. 		if(inc[s-1]==false)
  128. 			inc[s-1]=true;
  129. 		if(inc[d-1]==false)
  130. 			inc[d-1]=true;
  131. 		v[d-1].push_back(s-1);
  132. 	}
  133. 	for(int i=0;i<n;i++)
  134. 	sort(v[i].begin(),v[i].end());
  135. 	for(int i=0;i<n;i++)
  136. 		if(inc[i]==false)
  137. 			red.push_back(i+1);
  138. 	for(int i=0;i<n;i++)
  139. 		if(exp[i]==false&&inc[i]==true)
  140. 			visit(i);
  141. 	int idx=0;
  142. 	int len=red.size();
  143. 	if(ret==1)
  144. 	{
  145. 		cout<<"Sandro fails.";
  146. 		return 0;
  147. 	}
  148. 	while(!st.empty())
  149. 	{
  150. 		s.push(st.top());
  151. 		st.pop();
  152. 	}
  153. 	while(!s.empty())
  154. 	{
  155. 		while(idx<len&&s.top()+1>red[idx])
  156. 			cout<<red[idx++]<<" ";
  157. 		cout<<s.top()+1<<" ";
  158. 		s.pop();
  159. 	}
  160. 	while(idx<len)
  161. 		cout<<red[idx++]<<" ";
  162. 	return 0;
  163. }
Success #stdin #stdout 0s 3040KB
comments (?)
stdin
copy 
8 9
1 4
1 2
4 2
4 3
3 2
5 2
3 5
8 2
8 6
stdout
copy 
1 4 3 5 7 8 2 6
https://ideone.com/QCUmKY
For case:
3 2
3 1
3 2
my answer is 3 1 2
language:
C++ (gcc 8.3)
created:
10 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!