Pagini recente » Cod sursa (job #822420) | Cod sursa (job #1812046) | Cod sursa (job #781419) | Cod sursa (job #435354) | Cod sursa (job #1070315)
#include <fstream>
#include <sstream>
#include <deque>
#include <algorithm>
using namespace std;
void tarjan(int v, int N, deque<int>* adj,
int current_index, int* index, int* lowlink, deque<int>& S, char* is_in_queue,
int& component_id,
stringstream* ss)
{
index[v] = ++current_index; //assign a new index to the node; mark the node as read
lowlink[v] = current_index; //the initial guess for the components
S.push_back(v);
is_in_queue[v] = 1;
//parse the adjacency list of the node
for (deque<int>::iterator it = adj[v].begin(); it != adj[v].end(); it++) {
int w = *it;
//check if w does not have an index or it is already indexed and is in the queue
if (index[w] == 0) {
tarjan(w, N, adj, current_index, index, lowlink, S, is_in_queue, component_id, ss);
//update the lowlink of the current node
lowlink[v] = min(lowlink[v], lowlink[w]);
}
else if (is_in_queue[w]) {
lowlink[v] = min(lowlink[v], lowlink[w]);
}
}
//check if the current node is the root of a strong connex component
if (lowlink[v] == index[v]) {
component_id++;
int u;
while ( (u = S.back()) != v) {
S.pop_back();
is_in_queue[u] = 0;
ss[component_id] << u << ' ';
}
//once more for v
S.pop_back();
is_in_queue[v] = 0;
ss[component_id] << v << ' ';
}
}
//int e_026_componente_tare_conexe_tarjan()
int main()
{
string in_file = "ctc.in";
string out_file = "ctc.out";
int N, M;
const int MAX_N = 50000;
//the adjacency list
deque<int> adj[MAX_N + 1];
ifstream ifs(in_file);
ifs >> N >> M;
for (int k = 1; k <= M; k++)
{
int v1, v2;
ifs >> v1 >> v2;
adj[v1].push_back(v2);
}
ifs.close();
int index[MAX_N + 1], lowlink[MAX_N + 1];
char is_in_queue[MAX_N + 1];
stringstream ss[MAX_N + 1];
for (int v = 1; v <= N; v++) { index[v] = 0; is_in_queue[v] = 0; }
deque<int> S;
int current_index = 0, component_id = 0;
for (int v = 1; v <= N; v++) {
if (index[v] == 0) tarjan(v, N, adj, current_index, index, lowlink, S, is_in_queue, component_id, ss);
}
int no_of_components = component_id;
ofstream ofs(out_file);
ofs << no_of_components << endl;
for (int c = 1; c <= no_of_components; c++) ofs << ss[c].str() << endl;
ofs.close();
return 0;
}