Pagini recente » Cod sursa (job #3170230) | Cod sursa (job #2589895) | Cod sursa (job #2943712) | Cod sursa (job #556916) | Cod sursa (job #660347)
Cod sursa(job #660347)
#include <fstream>
#include <vector>
#include <stack>
#include <bitset>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
vector<int> G[100005] , aux;
vector< vector<int> > DD;
int N , M , lvl , low[100005] , idx[100005];
bitset<100005> in_stack;
stack<int> st;
void read_data()
{
int x , y;
fin>>N>>M;
for(;M;M--)
{
fin>>x>>y;
G[x].push_back(y);
}
}
void comp(const int nod)
{
int v; aux.clear();
do { aux.push_back(v = st.top());
st.pop();in_stack[v] = 0;
}while(v != nod);
DD.push_back(aux);
}
void df(const int node)
{
low[node] = idx[node] = ++lvl;
st.push(node); in_stack[node] = 1;
for(vector<int>::iterator w = G[node].begin();w!=G[node].end();++w)
if(idx[*w] == 0)
df(*w) , low[node] = min(low[node],low[*w]);
else
if(in_stack[*w] == 1) low[node] = min(low[node],low[*w]);
if(low[node] == idx[node])
comp(node);
}
void print()
{
fout<<DD.size()<<'\n';
for(int i = 0;i <(int) DD.size();++i) {
for(int j = 0;j <(int) DD[i].size();++j)
fout<<DD[i][j]<<' ';
fout<<'\n';
}
}
int main()
{
read_data();
for(int i = 1;i<=N;++i)
if(idx[i] == 0) df(i);
print();
return 0;
}