BZOJ 2208: [Jsoi2010]连通数( DFS )
2024-10-18 23:27:15
n只有2000,直接DFS就可以过了...
--------------------------------------------------------------------------
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cctype>
#define rep( i, n ) for( int i = 0; i < n; ++i )
#define clr( x, c ) memset( x, c, sizeof( x ) )
using namespace std;
const int maxn = 2000 + 5;
struct edge {
int to;
edge* next;
};
edge* pt;
edge* head[ maxn ];
edge EDGE[ maxn * maxn ];
void init() {
pt = EDGE;
clr( head, 0 );
}
inline void add_edge( int u, int v ) {
pt -> to = v;
pt -> next = head[ u ];
head[ u ] = pt++;
}
bool vis[ maxn ];
int ans = 0;
void dfs( int x ) {
ans++;
vis[ x ] = true;
for( edge* e = head[ x ]; e; e = e -> next ) if( ! vis[ e -> to ] )
dfs( e -> to );
}
int main() {
init();
int n;
cin >> n;
rep( i, n )
rep( j, n ) {
char c = getchar();
while( ! isdigit( c ) ) c = getchar();
if( c == '1' ) add_edge( i, j );
}
rep( i, n ) {
clr( vis, 0 );
dfs( i );
}
cout << ans << "\n";
return 0;
}
--------------------------------------------------------------------------
2208: [Jsoi2010]连通数
Time Limit: 20 Sec Memory Limit: 512 MB
Submit: 1499 Solved: 611
[Submit][Status][Discuss]
Description
Input
输入数据第一行是图顶点的数量,一个正整数N。 接下来N行,每行N个字符。第i行第j列的1表示顶点i到j有边,0则表示无边。
Output
输出一行一个整数,表示该图的连通数。
Sample Input
3
010
001
100
010
001
100
Sample Output
9
HINT
对于100%的数据,N不超过2000。
Source
最新文章
- Floyd判最小环算法模板
- #ifdef 的技巧用法
- [Mongo] 简单的操作命令
- Linux配置静态IP
- Spark Streaming揭秘 Day9 从Receiver的设计到Spark框架的扩展
- C语言变参函数/Variadic fucntion
- python引入导入自定义模块和外部文件
- C# partial修饰符_分部类_分部方法
- Controller的激活
- Python 协程/异步IO/Select\Poll\Epoll异步IO与事件驱动
- .NET Core 2.0 正式发布信息汇总
- Visual Studio Code 配置C++环境
- Akka(43): Http:SSE-Server Sent Event - 服务端主推消息
- Windows as a Service(4)——使用Intune管理Windows10更新
- Storm 常用命令
- MongoDB MapReduce用法简介
- Django目录
- JSP的简单介绍
- spring boot: ConfigurationProperties
- 177. Convert Sorted Array to Binary Search Tree With Minimal Height【LintCode by java】
热门文章
- iOS中的retainCount
- poj2196---Specialized Four-Digit Numbers
- 详解Spring中的CharacterEncodingFilter--forceEncoding为true在java代码中设置失效--html设置编码无效
- NET-A-PORTER为何难以模仿?_全文显示_生活福布斯中文网
- 解决mac插入U盘不显示标识问题
- mysql关联更新
- NAND FLASH
- 获取第上一个兄弟元素 屏蔽浏览器的差异(PreviousElementSibling)
- 重启sql server服务两种方式
- java 调用jdbc 实现excel和csv的导入和导出