Pagini recente » Cod sursa (job #1105751) | Cod sursa (job #1891869) | Cod sursa (job #2937465) | Cod sursa (job #1827980) | Cod sursa (job #1598151)
//============================================================================
// Name :
// Author : Teodor Cotet
// Version :
// Copyright : Your copyright notice
// Description : Strong Components, Kosaraju in O in O(N + M) C++, Ansi-style
//============================================================================
#include <fstream>
#include <vector>
#include <iostream>
#include <cstring>
#include <stack>
#include <set>
using namespace std;
const int NMAX = 100000;
const int MMAX = 200000;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int n; int m;
/*
* constructors for vector:
* v(int size)
* v(int size, TYPE value)
*/
vector< vector<int> > g(NMAX + 1, vector<int>(0));
vector< vector<int> > gTranspose(NMAX + 1, vector<int>(0));
stack<int> s;
vector< vector<int> > strongComp;
void read() {
fin >> n >> m;
for(int i = 0 ; i < m ; ++i) {
int x; int y;
fin >> x >> y;
g[x].push_back(y);
gTranspose[y].push_back(x);
}
}
void dfs(int curent, vector< vector<int> >& g, bool visited[]) {
visited[curent] = 1;
for(vector<int>::iterator it = g[curent].begin(); it != g[curent].end(); ++it) {
if(visited[*it] == 0)
dfs(*it, g, visited);
}
s.push(curent);
}
void dfsComponents(int curent, vector < vector<int> >& gTranspose, bool visited[]) {
visited[curent] = 1;
strongComp[strongComp.size() - 1].push_back(curent);
for(vector<int>::iterator it = gTranspose[curent].begin(); it != gTranspose[curent].end(); ++it)
if(visited[*it] == 0)
dfsComponents(*it, gTranspose, visited);
}
void getStrongConnected(vector< vector<int> >& g, vector< vector<int> >& gTranspose) {
/* do a topological sort first */
bool visited[NMAX + 1];
memset(visited, 0, n + 1);
for(int i = 1; i <= n ; ++i) {
if(visited[i] == 0)
dfs(i, g, visited);
}
/* if there is a node which "enters" in the first node from the topological sort, it
* means they are in the same strong connected component, so we make a dfs in the transpose graph
*/
memset(visited, 0, n + 1);
while( s.empty() == false) {
int node = s.top();
s.pop();
if(visited[node] == 0) {
strongComp.push_back(vector<int>(0));
dfsComponents(node, gTranspose, visited);
}
}
}
void solve() {
getStrongConnected(g, gTranspose);
fout << strongComp.size() << '\n';
for(unsigned i = 0 ; i < strongComp.size(); ++i) {
for(unsigned j = 0 ; j < strongComp[i].size(); ++j)
fout << strongComp[i][j] << " ";
fout << '\n';
}
}
int main() {
read();
solve();
return 0;
}