Pagini recente » Cod sursa (job #1759089) | Cod sursa (job #2911799) | Cod sursa (job #143149) | Cod sursa (job #2446855) | Cod sursa (job #1707430)
#include<fstream>
#include<iostream>
#include<vector>
#include<cstring>
using namespace std;
#define MAXN 100005
struct SCCLists {
int size;
SCCLists() {
size = 0;
}
vector<int> scc[MAXN];
};
struct Graph {
int n, m;
vector<int> adj[MAXN];
};
ifstream f("ctc.in");
ofstream g("ctc.out");
void computeScc(Graph& G, int source, int* visited, int* index, int* lowlink, int* stack, int &time, SCCLists& scc) {
//
visited[source] = 1;
index[source] = ++time;
lowlink[source] = time;
stack[++stack[0]] = source;
for (int it = 0; it < G.adj[source].size(); it++) {
if (!visited[G.adj[source][it]]) {
computeScc(G, G.adj[source][it], visited, index, lowlink, stack, time, scc);
}
}
int min = index[source];
for (int it = 0; it < G.adj[source].size(); it++) {
min = min > lowlink[G.adj[source][it]] ? lowlink[G.adj[source][it]] : min;
}
lowlink[source] = min;
if (lowlink[source] >= index[source]) {
scc.size++;
while (stack[stack[0]] != source) {
scc.scc[scc.size].push_back(stack[stack[0]]);
stack[0]--;
}
stack[0]--;
scc.scc[scc.size].push_back(source);
}
}
int main() {
//
SCCLists scc;
int visited[MAXN], index[MAXN], lowlink[MAXN], stack[MAXN];
Graph G;
int time = 0;
memset(visited, 0, sizeof(visited));
memset(index, 0, sizeof(index));
memset(lowlink, 0, sizeof(lowlink));
memset(stack, 0, sizeof(stack));
f >> G.n >> G.m;
for (int i = 1; i <= G.m; i++) {
int x, y;
f >> x >> y;
G.adj[x].push_back(y);
}
computeScc(G, 1, visited, index, lowlink, stack, time, scc);
g << scc.size << "\n";
for (int it = 1; it <= scc.size; it++) {
for (int jt = 0; jt < scc.scc[it].size(); jt++) {
g << scc.scc[it][jt] << " ";
}
g << "\n";
}
return 0;
}