topsort    发布于 2020-03-08   963人围观   0条评论

## 题解

E和F由于只需要&操作，所以可以用bitset来进行加速。

## 代码

```#include <bits/stdc++.h>
using namespace std;
int s,l,n;
const int maxn = 205;
vector<int>pos[maxn];
string a,b;
vector<string>name;
int id(string str){
return lower_bound(name.begin(),name.end(),str) - name.begin();
}
bitset<maxn>e[maxn],f[maxn];
vector<int>ans;
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> s >> l >> n;
name.reserve(s);
for(int i = 0;i < s;++i){
cin >> a;```
bitset topsort    发布于 2019-10-12   168人围观   0条评论

## 题解

mp[k][v] = mp[k][u]; ----> mp[k][v] |= mp[k][u];

## 代码

```#include <bits/stdc++.h>
using namespace std;
const int maxn = 305;
int d[maxn],tmp[maxn];
bitset<305>con[maxn];
queue<int>qk;
vector<int>g[maxn];
int n,m,q;
int a,b;
int c[maxn],vis[maxn];
void topsort(){
for(int i = 1;i <= n;++i)
con[i].reset();
for(int i = 1;i <= n;++i){
if(!c[i])
con[i][i] = 1;
vis[i] = 0;
}
for(int i = 1;i <= n;++i){
tmp[i] = d[i];
```
topsort DP    发布于 2019-07-07   330人围观   0条评论

## 代码

```#include <bits/stdc++.h>
using namespace std;
int get_num(){
int num = 0;
char c;
bool flag = false;
while((c = getchar()) == ' ' || c == '\r' || c == '\n');
if(c == '-')
flag = true;
else num = c - '0';
while(isdigit(c = getchar()))
num = (num<<3) + (num<<1) + c - '0';
return (flag ? -1 : 1) * num;
}
int n,m;
int x,y;
const int maxn = 1e5+5;
vector<int>g[maxn];
int f[maxn],d[maxn];
int inq[maxn];
int main(){
memset(d,0,sizeof(d));
n = get_num();
m = get_num();
for(int i = 1;i <= m;++i){
x = get_num();
y = get_num();
g[x].push_back(y);
d[y]++;
}
queue<int>q;
for(int i = 1;i <= n;++i){
if(!d[i])
q.push(i),inq[i] = 1;
f[i] = 1;
}
while(!q.empty()){
int x = q.front();
q.pop();```
topsort    发布于 2019-02-26   177人围观   0条评论

## Description

Teacher Mai has a kingdom consisting of n cities. He has planned the transportation of the kingdom. Every pair of cities has exactly a one-way road.

He wants develop this kingdom from one city to one city.

Teacher Mai now is considering developing the city w. And he hopes that for every city u he has developed, there is a one-way road from u to w, or there are two one-way roads from u to v, and from v to w, where city v has been developed before.

He gives you the map of the kingdom. Hope you can give a proper order to develop this kingdom.

## Input

There are multiple test cases, terminated by a line "0".

For each test case, the first line contains an integer n (1<=n<=500).

The following are n lines, the i-th line contains a string consisting of n characters. If the j-th characters is 1, there is a one-way road from city i to city j.

Cities are labelled from 1.

## Output

If there is no solution just output "-1". Otherwise output n integers representing the order to develop this kingdom.

## Sampl

2-SAT tarjan topsort    发布于 2019-02-07   444人围观   0条评论

## Description

You are given an undirected graph G = (V, E) containing N nodes and M edges. The nodes are numbered from 1 to N. A subset C of V is a vertex cover if for every edge (u, v) ∈ E, at least one of u and v belong to C. Note that C = V is always a vertex cover.
Consider a partition of V into two sets A and B. It is said to be a valid partition, if the following two conditions are satisfied: A should be a vertex cover. And for each i such that 1 ≤ i ≤ n/2, nodes 2i and 2i - 1 don't belong to the same set (i.e. one belongs to set A and the other to set B).
Determine if a valid partition exists. If it exists, provide an example of one valid partition.

## Input

The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains two space-separated integers N and M denoting the number of nodes and number of edges in the graph respectively.
Each of the following M lines contains two space-se