Pagini recente » Cod sursa (job #794268) | Cod sursa (job #2843335) | Cod sursa (job #188659) | Cod sursa (job #257401) | Cod sursa (job #2934201)
#include <fstream>
#include <vector>
#include <stack>
#include <cstring>
#include <bitset>
using namespace std;
ifstream in("ctc.in");
ofstream out("ctc.out");
#define MAX_N 100000
int n, m, strongConnectedComponentsNumber;
vector < vector <int> > graph, transposedGraph, components;
bitset <MAX_N + 1> visited;
stack <int> order;
void readGraph()
{
in >> n >> m;
graph.resize(n + 1);
transposedGraph.resize(n + 1);
for(int i = 1; i <= m; i++)
{
int a, b;
in >> a >> b;
graph[a].push_back(b);
transposedGraph[b].push_back(a);
}
}
void dfs1(int node)
{
visited[node] = 1;
for(int x : graph[node])
if(!visited[x])
dfs1(x);
order.push(node);
}
void dfs2(int node)
{
visited[node] = 1;
components[strongConnectedComponentsNumber].push_back(node);
for(int x : transposedGraph[node])
if(!visited[x])
dfs2(x);
}
void printComponents()
{
out << strongConnectedComponentsNumber << "\n";
for(int i = 0; i < strongConnectedComponentsNumber; i++)
{
for(int node : components[i])
out << node << " ";
out << "\n";
}
}
int main()
{
readGraph();
for(int i = 1; i <= n; i++)
{
if(!visited[i])
dfs1(i);
}
for(int i = 1; i <= n; i++)
visited[i] = 0;
components.resize(n);
while(!order.empty())
{
int node = order.top();
if(!visited[node])
{
dfs2(node);
++ strongConnectedComponentsNumber;
}
order.pop();
}
printComponents();
return 0;
}