Some appropriate ways to read a line in C/C++

Most of the ways that doesn’t require string size checking would possibly cause buffer overflow error

Using scanf

Code
char line[100]; // this string can contain maximum 99 characters
scanf("%[^\n]", line); // read every character until meet '\n'
scanf("%*c"); // = cin.ignore(1), ignore '\n' character for the next input statement

Using std::getline (string)

Systax: istream& getline(istream & is, string & str, char delim = ‘\n’);
“Extracts characters from is and stores them into str until the delim character is found“.
“The delim character is extracted and discarded (it is not stored)” .

So we don’t have to ignore newline character after this function.
And since string is essentially a vector ( built in data type), we also don’t have to specify its size (length). Thus, although this function does not care about the size of string, it’s safe to use.

Code C++

string s;
getline(cin, s);

Using std::istream::getline( char *)

Syntax: istream& getline(char * s, streamsize n, char delim = ‘\n’);
Extracts characters from istream object and stores them into s until the delim character is found or “n characters have been written to s (including the terminal null character)”.
The delim character is extracted and discarded.

So basically this function is the same as std::getline(string) function. Except we have to specify the maximum size of string because char is a primitive data type of C++.

Code C++

char line[100];
cin.getline(line, 100);

Using gets

Systax: char * gets( char * s);
“Reads characters from stdin and stores them as a C string into s until a newline character or the end-of-file is reached”
The newline character is not copied to s.

This function is unsafe because it does not have size checking, when the size of input string is equal or greater than the size we declare, it causes buffer overflow.

Code C

char line[100]; // contains maximum 99 characters
gets(line); // the size of input string should <= 99

Using fgets

Syntax: char * fgets(char * str, int num, FILE * stream);
“Reads characters from stream and stores them as a C string into str until (num-1) characters have been read or either a newline or the end-of-file is reached”.
The newline character is copied to str. So this function is quite not comfortable to use when the actual size of the string has 1 more character than you expect.
But it’s safer than gets because it has size cheking.

Code C

char line[100]; 
fgets(line, 100, stdin); 

Conclusion: should use getline

Happy coding

Advertisements

Read some tricky input format in C/C++

Problem 1

Format
Input:
+ 2 integer numbers on each line
+ end of input when 2 numbers are both equal to 0
Output:
+ sum of 2 numbers on each line

Code C

int a, b;
while( scanf("%d %d", &a, &b), (a || b) ) {
    printf("%d\n", a + b);
}

 

Code C++

int a, b;
while( cin >> a >> b, (a || b) ) {
    cout << a + b << '\n';
}

Problem 2

Format
Input:
+ 2 integer numbers on each line
Output:
+ sum of 2 numbers on each line

E.x 
Input:
1 2
3 4
Output:
3
7

Code C

int a, b;
while( scanf("%d %d", &a, &b) == 2 ) {
// while ( scanf("%d %d", &a, &b) != EOF ) {
    printf("%d\n", a + b);
}

Code C++

int a, b;
while( cin >> a >> b ) {
    cout << a + b << '\n';
}

Problem 3

Format
Input:
+ some integers on each line
Output:
+ sum of 2 numbers on each line

E.x 
Input:
1 2 3
4 5
6 7 8 9
Output:
6
9
30

Code C++

string s;
while( getline(cin, s) ) {
    istringstream iss(s);
    int sum = 0;
    int v;
    while( iss > v ) sum += v;
    cout << sum << '\n';
}

Happy coding

Kiểm tra đồ thị 2 phía

Một trong những định nghĩa của đồ thị 2 phía:
Một đồ thị vô hướng G với tập đỉnh V và tập cạnh E gọi là đồ thị 2 phía nếu có thể chia tập đỉnh V của nó thành 2 tập con rời rạc V1 và V2, sao cho với mỗi cạnh e thuộc E: có một đỉnh thuộc V1 và đỉnh kia thuộc V2.
2000px-simple-bipartite-graph-svg                                             Đồ thị 2 phía với 2 tập đỉnh rời rạc U, V

Tính chất:
Một đồ thị là 2 phía khi và chỉ khi nó được tô bằng 2 màu.

Thuật toán:
Tô 2 màu cho đồ thị bằng BFS và DFS: với đỉnh u đang xét:
– Nếu u không kề với đỉnh nào -> tô màu bất kỳ cho u
– Xét tập đỉnh v kề u:
+ Nếu v đã được tô màu và color[v] = color[u] -> đồ thị không tô được với 2 màu
+ Nếu v chưa tô màu, ta tô màu v với màu khác với màu của u.

Code: 
Format input:
+ dòng đầu n, m tương ứng với số đỉnh, số cạnh nối.
+ m dòng tiếp theo, mỗi dòng u, v là cạnh nối đỉnh u với v
Format output: 
+ Nếu đồ thị không thể tô màu, in ra -1
+ Ngược lại in ra 2 dòng, mỗi dòng là các đỉnh thuộc cùng một màu
Dữ liệu vào đảm bảo là một đồ thị liên thông (mạnh)
Code BFS
Code DFS

Độ phức tạp: 
O(M + N)

Bình luận về đoạn code DFS trên:

bool dfs(int u, int color = 1) {
    mark[u] = color;
    cl[2 - color].pb(u);

    for(int v : adj[u]) {
        if (!mark[v] && !dfs(v, 3 - mark[u])) return 0;
        if (mark[v] == color) return 0;
    }

    return 1;
}

Lời gọi DFS này sẽ lập tức trả về kết quả ngay khi nhận biết được đồ thị đang xét không phải là một đồ thị 2 phía.
Điều này rất nguy hiểm đối với một số bài toán mà đồ thị G bao gồm nhiều đồ thị con, xem xét đoạn code kiểm tra xem G có phải là một đồ thị bao gồm các đồ thị con 2 phía không :

bool dfs(int u, int color = 1) {
mark[u] = color;
cl[2 - color].pb(u);

for(int v : adj[u]) {
if (!mark[v] && !dfs(v, 3 - mark[u])) return 0;
if (mark[v] == color) return 0;
}

return 1;
}

// in main()
for(int u = 1; u <= V; u++) {
if (mark[v]) continue;
if (!dfs(u)) return "G không phải là tập các đồ thị 2 phía";
}
return "G là tập các đồ thị 2 phía";

Lời gọi DFS(u) sẽ trả về kết quả ngay khi nó nhận biết được đồ thị con đang duyệt không phải là đồ thị 2 phía, nó không cần phải duyệt hết tất cả các đỉnh mới biết thế; vậy nên sẽ có các đỉnh u của đồ thị con chưa được duyệt qua (đánh dấu mark[u]); và rất có thể tập hợp các đỉnh này sẽ được gọi ở lệnh lặp tiếp theo và được coi như một đồ thị con mới.

Để tránh vấn đề này, code được sửa lại rất đơn giản và dễ hiểu, chỉ cần không return ngay khi biết đó là một đồ thị không phải 2 phía. Hàm DFS sửa lại như sau:

bool dfs(int u, int color = 1) {
mark[u] = color;
cl[2 - color].pb(u);

int ans = 1;
for(int v : adj[u]) {
if (!mark[v] && !dfs(v, 3 - mark[u])) ans = 0;
if (mark[v] == color) ans = 0;
}

return ans;
}

Happy coding