#include <vector>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <string>
#include <algorithm>
#include <stack>
using namespace std;
vector<int> node[100001];
bool chk[100001];
int group[100001];
int cnt[100001];
stack<int> st;
int ret;
int grp;
void dfs(int x)
{
st.push(x);
chk[x] = true;
for(int i = 0 ;i < node[x].size();i++)
{
if( !chk[node[x][i]] )
dfs(node[x][i]);
}
}
void dfs2(int x)
{
chk[x] = true;
group[x] = grp;
for(int i = 0 ;i < node[x].size();i++)
{
if( !chk[node[x][i]] ) {
cnt[node[x][i]]++;
dfs2(node[x][i]);
}
else if( group[node[x][i]] == grp )
{
cnt[node[x][i]]++;
}
}
}
int main(void){
int n, m;
scanf("%d %d",&n, &m);
for(int i = 0 ;i < m ;i++)
{
int a, b;
scanf("%d %d", &a, &b);
node[a].push_back(b);
}
memset(chk,0,sizeof(chk));
for(int i = 1; i <= n;i++)
{
if( !chk[i] )
dfs(i);
}
memset(group, 0, sizeof(group));
grp = 0;
memset(chk,0,sizeof(chk));
memset(cnt,0,sizeof(cnt));
while(!st.empty()){
int next = st.top();
st.pop();
if(!chk[next])
{
dfs2(next);
grp++;
}
}
for(int i = 1 ;i <=n;i++)
{
if( cnt[i] > 1 )
{
printf("Not cactus\n");
return 0;
}
}
printf("Cactus\n");
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
4460 KB |
Output is correct |
| 2 |
Correct |
0 ms |
4460 KB |
Output is correct |
| 3 |
Incorrect |
4 ms |
4460 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
