Pagini recente » Cod sursa (job #771833) | Cod sursa (job #1636431) | Cod sursa (job #1673151) | Cod sursa (job #718517) | Cod sursa (job #2555379)
#include <cstdio>
#include <iostream>
#include <vector>
#include <stack>
#define NMAX 100001
#define GREEN 0 //not visited
#define YELLOW 1 //visited in the first DFS
#define RED 2 //visited in the second DFS
using namespace std;
int v, e; //nr of vertices, nr of edges
int nodeColor[NMAX]; //the color of the node (SEE DEFINITION)
int nrSCC = 0; //nr of strongly connected components
vector <int> graph[NMAX]; //adjacency lists
vector <int> graphTransposed[NMAX]; //the adjacency lists for the transposed graph
vector <int> SCC[NMAX]; //the strongly connected components
stack <int> st; //the topological sort of the graph
void read();
void DFS(int);
void DFStranspose(int);
void Kosaraju();
void topologicalSort();
void write();
int main() {
read();
Kosaraju();
write();
return 0;
}
void read()
{
freopen("ctc.in", "r", stdin);
scanf("%d%d", &v , &e);
int x, y;
for (int i = 1; i <= e; i++)
{
scanf("%d%d", &x, &y);
graph[x].push_back(y);
graphTransposed[y].push_back(x);
}
}
void Kosaraju()
{
topologicalSort();
while (!st.empty())
{
int node = st.top();
printf("%d ", node);
if (nodeColor[node] == YELLOW)
{
++nrSCC;
DFStranspose(node);
}
st.pop();
}
}
void topologicalSort()
{
for (int i = 1; i <= v; i++)
{
if (nodeColor[i] == GREEN)
DFS(i);
}
}
void DFS(int node)
{
nodeColor[node] = YELLOW;
for (unsigned int i = 0; i < graph[node].size(); i++)
{
int neighbour = graph[node][i];
if (nodeColor[neighbour] == GREEN)
DFS(neighbour);
}
st.push(node);
}
void DFStranspose(int node)
{
nodeColor[node] = RED;
SCC[nrSCC].push_back(node);
for (unsigned int i = 0; i < graphTransposed[node].size(); i++)
{
int neighbour = graphTransposed[node][i];
if (nodeColor[neighbour] == YELLOW) {
DFStranspose(neighbour);
}
}
}
void write()
{
freopen("ctc.out", "w", stdout);
printf("%d\n", nrSCC);
for (int i = 1; i <= nrSCC; i++)
{
for (auto j = SCC[i].begin(); j != SCC[i].end(); ++j)
printf("%d ", *j);
printf("\n");
}
fclose(stdout);
}