Pagini recente » Cod sursa (job #2966665) | Cod sursa (job #2943595) | Cod sursa (job #2988406) | Cod sursa (job #2628435) | Cod sursa (job #2107451)
#include <fstream>
#include <vector>
#include <stack>
#include <cstring>
using namespace std;
long int n, m;
ifstream f("ctc.in");
ofstream g("ctc.out");
stack<long int> s, p;
long int* preorder;
long int c;
bool* assigned;
vector<vector<long int> > sol;
struct graph{
vector<long int>* adj;
long int num_nodes;
graph(int nodes)
{
num_nodes = nodes;
adj = new vector<long int>[num_nodes];
}
void add_edge(long int u, long int v)
{
adj[u].push_back(v);
}
void scc()
{
while(!s.empty()) s.pop();
while(!p.empty()) p.pop();
c = 0;
if(preorder) delete[] preorder;
preorder = new long int[num_nodes];
memset(preorder, -1, sizeof(long int)* num_nodes);
if(assigned) delete[] assigned;
assigned = new bool[num_nodes];
memset(assigned, 0, sizeof(bool)* num_nodes);
for(long int i = 0; i < num_nodes; i++)
if(!assigned[i])
scc_dfs(i);
}
void scc_dfs(long int v)
{
preorder[v] = c++;
s.push(v);
p.push(v);
for(size_t i = 0; i < adj[v].size(); i++)
{
long int w = adj[v][i];
if(preorder[w] == -1)
scc_dfs(w);
else if(!assigned[w])
while(preorder[p.top()] > preorder[w])
p.pop();
}
if(p.top() == v)
{
sol.push_back(vector<long int>());
while(s.top()!= v)
{
sol.back().push_back(s.top()+1);
assigned[s.top()] = true;
s.pop();
}
sol.back().push_back(s.top()+1);
assigned[s.top()] = true;
s.pop();
p.pop();
}
}
};
int main()
{
f >> n >> m;
graph gr(n);
for(long int i = 0; i < m; i++)
{
long int u, v;
f >> u >> v;
gr.add_edge(u-1, v-1);
}
gr.scc();
g << sol.size() << '\n';
for(long int i = 0; i < sol.size(); i++)
{
for(long int j = 0; j < sol[i].size(); j++)
g << sol[i][j] << ' ';
g << '\n';
}
return 0;
}