Pagini recente » Cod sursa (job #630175) | Cod sursa (job #2430778) | Cod sursa (job #1376117) | Cod sursa (job #1190478) | Cod sursa (job #1070373)
#include <fstream>
#include <sstream>
#include <deque>
#include <algorithm>
using namespace std;
namespace e_026_componente_tare_conexe {
const int MAX_N = 100000;
int N;
int *index, *lowlink;
int current_index = 0, component_id = 0;
char* is_in_queue;
deque<int> adj[MAX_N];
deque<int> S;
deque<deque<int>> SCCs;
deque<int> scc;
void tarjan(int v)
{
current_index++;
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);
//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++;
scc.clear();
int u;
do {
u = S.back();
S.pop_back();
is_in_queue[u] = 0;
scc.push_front(u);
} while (u != v);
SCCs.push_back(scc);
}
}
}
//int e_026_componente_tare_conexe_tarjan()
int main()
{
using namespace e_026_componente_tare_conexe;
string in_file = "ctc.in";
string out_file = "ctc.out";
int M;
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();
index = new int[N+1], lowlink = new int[N+1];
is_in_queue = new char[N+1];
for (int v = 1; v <= N; v++) { index[v] = 0; is_in_queue[v] = 0; }
for (int v = 1; v <= N; v++) if (index[v] == 0) tarjan(v);
int no_of_components = component_id;
ofstream ofs(out_file);
ofs << no_of_components << endl;
for (int c = 1; c <= no_of_components; c++) {
deque<int>& scc = SCCs.front();
for (deque<int>::iterator it = scc.begin(); it != scc.end(); it++) ofs << *it << ' ';
ofs << endl;
SCCs.pop_front();
}
ofs.close();
//relsease the memory
delete[] index;
delete[] lowlink;
delete[] is_in_queue;
return 0;
}