Pagini recente » Cod sursa (job #2106440) | Cod sursa (job #3138068) | Cod sursa (job #3153331) | Cod sursa (job #2904516) | Cod sursa (job #2871543)
#include <bits/stdc++.h>
#include <fstream>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
#define ll long long
const int NMAX = 100000;
vector<int>g[NMAX+5];
int low_link[NMAX+5], ids[NMAX+5];
bitset<NMAX+5>in_stack;
stack<int> st;
vector< vector<int> >strong_components;
int index;
void dfs_tarjan(int node){
st.push(node);
in_stack[node] = 1;
ids[node] = index;
low_link[node] = index;
index++;
for(int i =0; i < g[node].size(); i++){
int x = g[node][i];
if(ids[x] == 0)
dfs_tarjan(x);
if(in_stack[x])
low_link[node] = min(low_link[node], low_link[x]);
}
if(ids[node] == low_link[node]){
vector<int> strong_component;
int x = -1;
do{
x = st.top();
in_stack[x] = 0;
low_link[x] = ids[node];
strong_component.push_back(x);
st.pop();
}
while(x != node);
strong_components.push_back(strong_component);
}
}
void tarjan(int n){
index = 1;
int scc = 0;
for(int i =1; i <=n; i++)
{
if(ids[i] == 0){
dfs_tarjan(i);
}
}
}
int main(){
int n, m, x, y;
fin>>n>>m;
for(int i =1; i <=m; i++){
fin>>x>>y;
g[x].push_back(y);
}
tarjan(n);
fout<<strong_components.size()<<"\n";
for(int i =0 ; i < strong_components.size(); i++)
{
for(int j =0; j < strong_components[i].size(); j++)
fout<<strong_components[i][j]<<" ";
fout<<"\n";
}
return 0;
}