Pagini recente » Cod sursa (job #2806700) | Cod sursa (job #2751086) | Cod sursa (job #2957239) | Cod sursa (job #2981238) | Cod sursa (job #1496212)
#include<iostream>
#include<fstream>
#include<cmath>
#include<algorithm>
#include<vector>
#include<bitset>
#include<cstring>
#include<queue>
#include<stack>
#define ull unsigned long long
#define ll long long
#define pb push_back
#define FOR(a,b,c) for (int a=b;a<=c; ++a)
#define ROF(a,b,c) for (int a=b;a>=c; --a)
#define Nmax 100010
// algoritmul tarjan
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
int N,M,nrcomp,nr;
int index[Nmax],lowest[Nmax];
vector<int> v[Nmax];
vector<int> componente[Nmax];
vector<int> st;
bitset<Nmax> instack;
void dfs(int);
int main()
{
f>>N>>M;
FOR (i,1,M) {
int x,y;
f>>x>>y;
v[x].pb(y);
}
FOR (i,1,N) {
if (!index[i]) {
dfs(i);
}
}
g<<nrcomp<<'\n';
FOR (i,1,nrcomp) {
for (unsigned int k=0;k<componente[i].size();++k) {
g<<componente[i][k]<<' ';
}
g<<'\n';
}
f.close();g.close();
return 0;
}
void dfs(int nod) {
index[nod]=lowest[nod]=++nr;
st.pb(nod);
instack.set(nod,1);
for (unsigned int k=0;k<v[nod].size();++k) {
if (!index[v[nod][k]]) {
dfs(v[nod][k]);
lowest[nod]=min(lowest[nod],lowest[v[nod][k]]);
}
else if (instack.test(v[nod][k])) {
lowest[nod]=min(lowest[nod],lowest[v[nod][k]]);
}
}
if (index[nod]==lowest[nod]) {
++nrcomp;
int top;
do {
top=st.back();
st.pop_back();
instack.set(top,0);
componente[nrcomp].pb(top);
}
while (top!=nod);
}
}