#include<iostream>
#include<cstdio>
#include<stack>
#include<queue>
#include<cstring>
#include<cmath>
using namespace std;
#define MAX 105
int deg[MAX];
int n, e;
struct compare
{
bool operator() (const int& l, const int& r)
{
return l>r;
}
};
vector<int>vec[MAX];
vector<int>rev[MAX];
priority_queue<int, vector<int>, compare > prq;
queue<int>myq;
void visit()
{
int i, j, u, v;
for(i=1; i<=n; i++)
{
if(deg[i]==0)
{
prq.push(i);
}
}
while(!prq.empty())
{
u=prq.top();
prq.pop();
myq.push(u);
for(i=0; i<rev[u].size(); i++)
{
v= rev[u][i];
deg[v] -= 1;
if(deg[v]==0)
{
prq.push(v);
}
}
}
}
int main()
{
int i, j;
int u, v, m;
while(scanf("%d%d", &n, &e)!=EOF)
{
memset(deg, 0, sizeof(deg));
for(i=0; i<=n; i++)
{
vec[i].clear();
rev[i].clear();
}
while(!prq.empty())
{
prq.pop();
}
while(!myq.empty())
{
myq.pop();
}
for(i=0; i<e; i++)
{
cin >> u >> m;
for(j=0; j<m; j++)
{
cin >> v;
deg[u]++;
rev[v].push_back(u);
}
}
visit();
i=0;
while(!myq.empty())
{
if(i) printf(" ");
printf("%d", myq.front());
myq.pop();
i=1;
}
printf("\n");
}
}
#include<cstdio>
#include<stack>
#include<queue>
#include<cstring>
#include<cmath>
using namespace std;
#define MAX 105
int deg[MAX];
int n, e;
struct compare
{
bool operator() (const int& l, const int& r)
{
return l>r;
}
};
vector<int>vec[MAX];
vector<int>rev[MAX];
priority_queue<int, vector<int>, compare > prq;
queue<int>myq;
void visit()
{
int i, j, u, v;
for(i=1; i<=n; i++)
{
if(deg[i]==0)
{
prq.push(i);
}
}
while(!prq.empty())
{
u=prq.top();
prq.pop();
myq.push(u);
for(i=0; i<rev[u].size(); i++)
{
v= rev[u][i];
deg[v] -= 1;
if(deg[v]==0)
{
prq.push(v);
}
}
}
}
int main()
{
int i, j;
int u, v, m;
while(scanf("%d%d", &n, &e)!=EOF)
{
memset(deg, 0, sizeof(deg));
for(i=0; i<=n; i++)
{
vec[i].clear();
rev[i].clear();
}
while(!prq.empty())
{
prq.pop();
}
while(!myq.empty())
{
myq.pop();
}
for(i=0; i<e; i++)
{
cin >> u >> m;
for(j=0; j<m; j++)
{
cin >> v;
deg[u]++;
rev[v].push_back(u);
}
}
visit();
i=0;
while(!myq.empty())
{
if(i) printf(" ");
printf("%d", myq.front());
myq.pop();
i=1;
}
printf("\n");
}
}
No comments:
Post a Comment